On debian-like, remove host keys and run dpkg-configure openssh-server.
On redhat-like, remove host keys and restart sshd.
---------------------------------------------
Not vulnerable, not a bad practice. Newer algorithms are faster (in practice not perceptible, people usually don't need state of the art performance for SSH connections), with smaller keys and probably better algorithms (not subject to side channel attacks, which are still hard to abuse) but RSA is not broken. It may be in a few years with quantum computing but it's still far to be sure.
https://www.schneier.com/blog/archives/2021/03/no-rsa-is-not... updated last december.
No need to rekey all accounts or servers, just switch to ecdsa or ed25519 progressively.
The systems you are trying to SSH to are using outdated host keys, you need to actually update to get security fixes, it will regenerate host keys.
You shouldn't be worried about this CVE, it sounds like you have quite a few years of CVE's you've neglected to patch anyways.
No you don't. rsa-sha2-256 and rsa-sha2-512 are still enabled by default and can use the same key.