The message you are seeing is a separate issue. It is asking you to confirm that the host you're connecting to is really the one you expect it to be. From the server, you can get the fingerprint by running
ssh-keygen -l -f /etc/ssh/ssh_host_rsa_key.pub. Then, when you're connecting remotely for the first time, you can make sure that the fingerprints match.
Host keys, seen in action here, address the problem of man in the middle attacks — perhaps DNS has been subverted, and you're connecting to a competitor's machine instead of your own. That machine gathers your credentials and transparently forwards your connection to the real server, stealing your information without you knowing. Making sure the host key matches prevents this from happening unless the attacker has actually stolen your server's public key.
A problem remains, though — how do you know which key is right? After the first connection, the public key is stored in your
~/.ssh/known_hosts file, so subsequent connections are fine. But the first time, you either need some out-of-band way of getting the fingerprint, or else you follow the "TOFU" model: trust-on-first-use.
But none of this has anything to do with passwords vs. keys, except that both keys and passwords could be stolen via this attack -- in a sense, it's the vulnerability you're asking for.
There's (at least) three reasons passwords are worse than keys:
- They can be brute-forced. A typical user-selected 8-character password has around 30 bits of guessing-entropy. An ssh public/private key pair is 1024 bits or larger. It's effectively impossible to brute-force an ssh key, but automated password guessing happens all the time.
- They can be dumb. Users routinely select horrible passwords, even with restrictions in place, and they tend to use harder passwords in multiple places. This obviously makes attacks easier.
- Passwords can be stolen remotely. When you're using SSH, the password is encrypted on the wire, but it's very common for the ssh server to be replaced on compromised systems with one that logs all passwords. With keys, the private key stays on the local system and is never sent at all, and so it can't be stolen without actually compromising the client machine.
Additionally, ssh keys offer convenience when used with something like
ssh-agent — you get the hassle-free operation of connecting without re-authenticating each time, while still maintaining a reasonable degree of security.
There's no significant advantage in asking for both, as someone who has enough access to steal the private key can fairly easily steal the user's password as well. If you need more security than this, consider looking into a two-factor authentication system like RSA SecurID or WiKID.