The different types of modern (2021) SSH keys (and some opinions)
Back in 2014 I wrote about what I knew about the then-current different types of SSH keys. Things have changed around a bit since then, so it's time for an update.
Modern versions of SSH support three different types of public key cryptography for common use; RSA, ECDSA, and Ed25519. Both ECDSA and Ed25519 use elliptic curve cryptography, while RSA is based on integer factorization. SSH once supported DSA public key cryptography, but it has been deprecated since the 7.0 release of OpenSSH in 2017 (search for 'ssh-dss'). OpenSSH supports FIDO/U2F hardware authenticators with ECDSA and Ed25519 keys since OpenSSH 8.2, and supports SSH key certificates for all key types.
To actually use SSH host and user keys, OpenSSH must also pick a
signature scheme. Ed25519 keys only have a single signature scheme,
but ECDSA and RSA keys have several different ones. OpenSSH is on the
path to deprecate the "ssh-rsa" signature scheme, but this doesn't
deprecate RSA keys in general.
OpenSSH lists RSA keys in your
file in a scheme independent way, but lists ECDSA keys in a
scheme-dependent one. There is probably a cryptographic reason for this.
OpenSSH has supported ECDSA keys since OpenSSH 5.7, released at the start of 2011, and Ed25519 keys since OpenSSH 6.5, released at the start of 2014. The stronger RSA key algorithms that OpenSSH now wants you to use have been supported since OpenSSH 7.2, released in February of 2016; however, these were only officially standardized in an RFC in RFC 8332, released in March 2018. By now, support for these key types and signature schemes has propagated to every operating system release that uses OpenSSH and isn't a complete and utter zombie. However, support for them has definitely not propagated into all sorts of SSH servers and clients that are not using OpenSSH, and what support that has propagated may be partial support (some environments support using but not generating Ed25519 keys, for example, and may not yet support the additional RSA signature schemes).
(Unlike in the past, the Gnome Keyring SSH agent implementation apparently does now support Ed25519 keys, apparently since some time in 2018.)
I think that OpenSSH can have different preferred key signature
algorithms for user keys and for host keys, and the preference order
for them can differ between different OpenSSH versions and different
people's builds of them. If I'm reading the official OpenSSH
ssh_config manpage correctly,
the current upstream OpenSSH preference is Ed25519, ECDSA, and then
RSA. The current preferences on Linux distributions can be opaque,
but I think that they generally prefer ECDSA over Ed25519 for host
keys, but Ed25519 over ECDSA for user keys. Don't ask me.
Here today in 2021, I think the consensus is definitely that Ed25519 is the best OpenSSH key type, probably with ECDSA as your second choice. See, for example, the Arch Wiki on choosing the key type, which has a long discussion with links for further reading. I don't know if non-OpenSSH support for ECDSA keys is much different than non-OpenSSH support for Ed25519 keys, although ECDSA in OpenSSH was standardized much earlier (in RFC 5656, from 2009; see OpenSSH Specifications).
As a pragmatic matter, I think that most devices today that don't support Ed25519 keys will probably be using SSH implementations that only support very basic things, like RSA keys with the old "ssh-rsa" key signature algorithm. They may also only support old key exchange algorithms and ciphers. Fortunately OpenSSH has not yet actually removed the code to support things like 'diffie-hellman-group1-sha1', and you can re-enable them if necessary following the information in OpenSSH Legacy Options.