Bye bye RSA keys?

The signature algorithm doesn't relate to the key size, though OpenSSH will refuse RSA keys <1024 bits. Practically, you should use at least 2048 bit keys (this is the default for ssh0-keygen).

All existing ssh-rsa keys can be used with the newer rsa-sha2-256/512 signature types. Whether these are supported though is down to the ssh client and server in question, and the easiest way to find out whether both offer those algorithms is to try the recipe in the release notes ("ssh -oHostkeyAlgorithms=-ssh-rsa")