The key format has not changed. The only thing that changes is the _signature_ format that's sent during each authentication handshake.

What makes everything confusing is that originally in SSHv2, the key type and the signature type used to be defined in combination. (For example, the same "ssh-rsa" identifier was defined to mean RSA keys _and_ RSA/SHA-1 signatures.) So changing the signature process _would_ have meant assigning a new key type identifier, and that would have meant generating a new key.

However, protocol extensions have been developed to avoid this, and modern SSH clients will automatically negotiate the signature types whenever RSA keys are involved. If you connect with `ssh -v` you will notice a few additional packets being exchanged:

    debug1: SSH2_MSG_EXT_INFO received
    debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519,ssh-rsa,rsa-sha2-256,
                                rsa-sha2-512,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,
                                ecdsa-sha2-nistp521>

So you can continue using "ssh-rsa" keys &ndash; you only need to upgrade the software on both ends to something reasonably recent, and it will automatically start producing "rsa-sha2-256" signatures from that key. (For example, you might need to install a new version of PuTTY and Pageant, and you might have troubles with older versions of gpg-agent.)

---


Note that this is a different situation from previous SHA-1 usage in X.509 (HTTPS) certificates.

Certificates, such as those used in HTTPS (X.509), had to be replaced because they hold a signature _inside_ &ndash; each certificate is signed by the parent CA at the time it is issued. This long-term signature stored in the certificate is a completely separate thing and unrelated to the short-term signatures that are made during each connection and then thrown away.

So if your workplace uses the so-called "OpenSSH certificates" (e.g. you have files whose names end with `-cert.pub`), you might need to have _those_ re-issued and `ssh-keygen -Lf <file>` will tell you whether they were signed using RSA/SHA-1 or RSA/SHA-256.

But if you just generated a key yourself, then it does not have signature inside, so there's nothing you need to do with it.

---

> I tried checking the type of the key with ssh-keygen -l -f key and it shows me that it is indeed SHA256 type

No, that is not what ssh-keygen shows at all. The `-l` option is showing you the key's "fingerprint" and it's telling you that it used SHA256 to compute this fingerprint &ndash; but it has nothing to do with the key's type, nor with how the key will actually be used. The fingerprint is just a hash that was computed right now in order to be shown to _you_.

(Remember that previously SSH software used to show MD5-based key fingerprints &ndash; even though there was no MD5 usage in the actual SSHv2 protocol.)