Fedora and CentOS automatically regenerate SSH host keys on bootup if the key files are missing. This makes it easy to trigger regeneration as you simply remove the keys, and reboot the server. Other distributions are not quite as forgiving and require manual intervention. These are the steps I've used on Debian to get updated host keys.
rm /etc/ssh/ssh_host_* ssh-keygen -f /etc/ssh/ssh_host_rsa_key -N '' -q -t rsa ssh-keygen -f /etc/ssh/ssh_host_ecdsa_key -N '' -q -t ecdsa ssh-keygen -f /etc/ssh/ssh_host_ed25519_key -N '' -q -t ed25519 ls /etc/ssh/*key* -lsh systemctl restart sshd