As chaves são geradas automaticamente quando você instala o servidor openssh.
Para criar manualmente um novo conjunto de chaves,
Primeiro, exclua as chaves do host ssh antigo. No servidor,
sudo rm -f /etc/ssh/ssh_host_*
Em seguida, crie novas chaves
sudo dpkg-reconfigure openssh-server
Você verá
Criando a chave RSA do SSH2; isto pode tomar algum tempo ... Criando chave DSA SSH2; isto pode tomar algum tempo ... Reiniciando o servidor do SecureBSD Secure Shell: sshd.
Seus clientes podem receber uma mensagem quando fizerem login:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@ @ AVISO: A IDENTIFICAÇÃO DO ALOJAMENTO REMOTO MUDOU! @ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@ É POSSÍVEL QUE ALGUÉM ESTÁ FAZENDO ALGO PERDIDO! Alguém pode estar escutando você agora mesmo (ataque man-in-the-middle)! Também é possível que a chave do host RSA tenha acabado de ser alterada.
...
Em caso afirmativo, faça os clientes executarem
ssh-keygen -R hostname
em que hostname é o nome do servidor.