Para tornar mais fácil para os clientes, eu usaria apenas a mesma chave de host em ambas as máquinas. Basta copiar uma das chaves (a do servidor atualmente em uso) para a segunda máquina. As chaves estão em /etc/ssh/ssh_host_*
.
Outra opção é desativar a verificação da chave do host nos clientes. Isso pode ser feito ajustando seu ssh_config
para usar:
Host myservice.mycompany.uk
StrictHostKeyChecking