Está a tentar encontrar chaves privadas no seu computador; o computador remoto teria a chave pública. Computadores remotos nunca devem ter sua chave privada (a menos que seja um computador sob seu controle).
Parece que você está com a autenticação do GSS ativada. Na linha de comando, é possível desativá-la com algo como ssh -o GSSAPIAuthentication=no [email protected] .
Se isso funcionar, provavelmente seria mais fácil desativar as conexões padrão adicionando GSSAPIAuthentication no na seção Host * do arquivo ~/.ssh/config (ou no arquivo ssh_config do sistema). Se você precisar dele para servidores locais, você pode adicionar uma seção Host *.my_company.com com ela novamente ativada.