O outro adicionaria automaticamente também, mas isso não acontece porque já tem uma entrada correspondente com uma chave diferente. Eu geralmente desabilito a verificação usando StrictHostKeyChecking (e excluindo known_hosts se ficar muito irritado, você pode precisar recriá-lo manualmente se, por algum motivo, ele não criar automaticamente um novo known_hosts ):
ssh -o StrictHostKeyChecking=no host
Você pode precisar definir CheckHostIP também ( -o CheckHostIP=no ).