It depends heavily on your threat model. Just about any key is an improvement over using passwords to authenticate. If you want protection from state-level actors, you need to be really careful and consistent.

Regarding key types:

- DSA keys (ssh-dss) suffer from several issues (fewer bits, bad RNGs in Debian, other issues), and modern versions of OpenSSH deprecate it.

- RSA is pretty standard, and generally speaking is fairly secure for key lengths >=2048. RSA-2048 is the default for ssh-keygen, and is compatible with just about everything.

- ECDSA is largely considered compromised because the constants NIST chose for the cryptosystem weren't well documented how they got them, and the assumption is that the NSA chose them to provide a "backdoor" (so it would provide the same security for a general attacker, but significantly easier for them). This was confirmed as being theoretically possible, and there is of course concern that the NSA could potentially leak those constants, instantly breaking the security of this cryptosystem.

- ED25519 is more or less the same as ECDSA, but was put together by DJB. The big advantage here is speed. EC crypto is much faster to sign, slightly slower to verify, and equivalent security can be achieved with fewer key bits.

- Notes for the future: both RSA and ED25519 become insecure against quantum computing (integer factorization and discrete log are both in BQP).

Generally, use RSA if you work with older servers that only support it, or ED25519 if you like shiny things. Otherwise it's a bit of a tossup.

Regarding using separate keys:

- I follow the philosophy that a private key should never leave the host it was generated on. If you aren't sharing keys between machines, you remove the risk that you'll accidentally share it publicly.

- Beyond that, I'd recommend at a minimum having separate work/personal keys. Keeping separate keys for each user/host you want to log into is a tad excessive, but can be useful for key revocation/rotation.

Regarding passphrases on keys:

- Yes. FDE is sometimes trivial to bypass, and you want to be protected in case someone sets your ~/.ssh folder to be synced to dropbox/samba/etc. You can use an agent to keep the decrypted keys in memory, but I'd avoid using agent forwarding.

Regarding bastion hosts:

- You didn't ask about this, but it is essential for a "best practice" setup.

- Bastion hosts are small VPS hosts that basically run sshd and have a static IP. You disallow any ssh traffic except from your bastion hosts to your servers.

- You'll want to have at least 2 bastion hosts with different hosting services, in case one isn't available.

- Run sshd on your bastion host on a port other than 22. Not for security, but for reducing log volume.

- Run fail2ban on your bastion host, even if you've disabled password authn. Again, not for security, but for reducing log volume.

- Set up fail2ban to alert when a new IP successfully logs in.

Other stuff:

- SSH can use certificates for authentication, and this can make the key distribution problem much easier to solve. I have a script that makes this easier.

- Push for everyone in your organization to use SSH keys, and only SSH keys.

- Defense in depth. All it takes is skipping one step and you expose yourself. Assume that something that was exposed has been compromised. An attacker only needs to succeed once.

tl;dr - the defaults are fine and password protect your keys.