Today I discovered about what was to me a confusing and alarming note in the OpenSSH 8.3 release notes (via), which has actually been there since OpenSSH 8.2. Here is the text (or the start of it):

Future deprecation notice

It is now possible to perform chosen-prefix attacks against the SHA-1 algorithm for less than USD$50K. For this reason, we will be disabling the "ssh-rsa" public key signature algorithm by default in a near-future release.

[...]

For a sysadmin this is somewhat hair raising on initial reading. We have a lot of users with ssh-rsa keys in their authorized keys files, and it would be very disruptive if they someday suddenly had to update those files, either to have their current keys accepted or to change over to new ones. However, there seemed to be a lot of confusion among people discussing this about what it affected (with some people saying that it only affected host keys and personal keypairs should be fine, for example). So I did my best to dig into this, and the summary is I don't think this requires most people to change host key or personal key configurations. I have two reasons for coming to believe this.

On a practical level, the announcement specifically says that one of your alternatives is that you can continue to use 'the same key type' (ie RSA keys) but with RFC8332 RSA SHA-2 signature algorithms. Then if we look in the very latest OpenSSH sshd manpage, its section on the authorized_keys file format doesn't have a special key type for 'RSA with RFC8332 RSA SHA-2 signature algorithms'; the only RSA key type is our old friend 'ssh-rsa'. Nor does ssh-keygen have an option for key generation other than 'generic RSA'. Since there's no particular way to specify or generate RSA keys in a key format other than what we already have, it seems that existing existing ssh-rsa authorized_keys lines pretty much have to keep working.

On a general level, there are two things involved in verifying public keys, the pair of keys themselves and then a signature algorithm that's used to produce a proof that you have access to the private key. While each type of keypair needs at least one signature algorithm in order to be useful, it's possible to have multiple algorithms for a single type of key. What OpenSSH is moving toward deprecating is (as they say) the signature algorithm for RSA keys that uses SHA-1; they continue to support two further SHA-2 based signature algorithms for RSA keys. Where the confusion comes in is that OpenSSH uses the label 'ssh-rsa' for both the name of of the RSA keytype in authorized_keys files and similar places and the name of the original signature algorithm that uses RSA keys. In the beginning this was fine (there was only a single signature algorithm for RSA keys), but now this is confusing if you don't read carefully and see the difference.

For OpenSSH host keys specifically, a server with RSA host keys is fine if one of two things are true; if it supports the additional signature algorithms for RSA keys, or if it has additional host key types. A server is only in trouble (in the future) if it has only a RSA host key and only supports the SHA-1 based 'ssh-rsa' signature algorithm. For personal RSA keypairs, the basic logic is the same; you're fine if the server (and your client) support the additional signature algorithms for RSA keys or if you have non-RSA keys of a keytype that both ends support (sadly not everyone supports Ed25519 keys).