Remova as chaves antigas e execute:
ssh-keygen -A restorecon /etc/ssh/ssh_host_*
Nota: moduli
e (obviamente) sshd_config
não são chaves e não devem ser removidas.
As teclas do host também podem ser geradas uma a uma usando:
for type in rsa dsa ecdsa ed25519; do
ssh-keygen -t ${type} -N "" -f /etc/ssh/ssh_host_${type}_key
done
restorecon /etc/ssh/ssh_host_*