Setting up SSH keys is pretty easy. I know that the UK hosting provider
The Bunker simply don't give you a password. They ask for a public key, verify the fingerprint with you on the phone and then put it in place for you to log in. Amazon EC2 also doesn't do passwords by default but generates both public and private and gives you the private key to use to log in.