A impressão digital da sua máquina provavelmente está localizada em /etc/ssh em
-
ssh_host_rsa_key,ssh_host_dsa_keyou -
ssh_host_key.pub
Você deve conseguir alterar manualmente o arquivo e reiniciar o daemon SSH. Uma reinstalação do servidor SSH também deve gerar uma nova chave de host.