How do they authenticate* you?
I'm also interested in that, but
I can request any account encrypted key and try to brute force it offline
This is likely wrong, any password would allow you to produce a valid key from an encrypted key, it will not be a correct key, so you will fail during decryption, but it will take a lot of time to check and may not be easy to automate.
Regarding the auth, they may provide you with a challenge that is encrypted with your public key, and if you have decrypted it correctly, authenticate you, but I don't know how it's done or should be done.