But I can still rekey everything using my master password and the encrypted private key is still stored on keybase's servers, right? (or something like that)
I'm going to lose the paper key just like I lost my 5 BTC wallet just before the great Bitcoin boom of 2013.
Depends on how you set up the key initially. I don't know if it's still possible, but at some point in the past you could specify your own master key that isn't stored on their servers. My account was one of those, so once I lost access to my computers/paper key, I also had lost access to the PHP key and therefore had to essentially start fresh.
The only pain is that you have to re-verify all your services.
That way, you don't have to rekey all your services if you lose it and access to all your devices, like I did.
Protip: Use the paper key. Keep it safe. You never know when you'll have to use it.