Você pode mover todas as chaves de todos os servidores para a única e modificar sshd_config para listar todas elas (opções HostKey ). Então o servidor deve oferecer todas as chaves.
Também dependendo da versão do openssh (se você estiver acima de 6.8), os clientes pegarão todas as chaves ao se conectar e depois de algum tempo você poderá remover as antigas.