Geralmente você deve ser muito cauteloso quando chegar
WARNING - POTENTIAL SECURITY BREACH!
The server's host key does not match the one PuTTY has cached in the registry.
É uma indicação do ataque MITM .
Veja também a documentação do PuTTY para ADVERTÊNCIA - VIOLAÇÃO POTENCIAL DE SEGURANÇA! / a> (qual é a parte principal da mensagem, que você de alguma forma omitiu na sua pergunta).
Você nunca recebe esta mensagem para um novo servidor. A menos, é claro, que o novo servidor reutilize o endereço IP / nome do host de algum servidor descartado. Nesse caso, não há problema em ignorar o aviso.
É, claro, uma chave pública que é armazenada em cache pelo PuTTY. Uma chave privada é secreta e não deve ser acessível a ninguém, exceto pelo administrador do servidor. Portanto, não há como o SSH client conseguir.
O servidor pode, de fato, ter um número de pares de chaves para diferentes algoritmos (um para cada algoritmo, como RSA, DSA, ECDSA, ED25519). O cliente e o servidor concordarão com o melhor algoritmo a ser usado (o melhor dos suportados pelo servidor e pelo cliente).
Os pares de chaves geralmente são armazenados em /etc/ssh
(no Linux com OpenSSH).
Embora o texto da sua pergunta indique que você pode confundir o par de chaves servidor / host com o par de chaves que você usa para autenticar no servidor.
Veja o artigo meu em Noções básicas sobre pares de chaves SSH .