Primeiro, sugiro, se puder, remover o + purge, reinstalar o openssh-client / server nas três máquinas e remover cada ~ / .ssh, para que você comece de uma situação limpa.
Em seguida, siga esta página wiki do ubuntu que trata mais especificamente da configuração das chaves ssh.
Por último, tenha em mente o seguinte problema: de debian ssh wiki :
% bl0ck_qu0te%