As seguintes linhas podem ser muito enganadoras:
debug3: Incorrect RSA1 identifier
debug3: Could not load "/home/kerem/.ssh/id_dsa" as a RSA1 public key
Outra resposta sugere:
So, may be the reason is with the keys on your client machine? Try to
regenerate them.
Por experiência, posso dizer que esse problema pode ser causado pela configuração do servidor, embora as mensagens pareçam estritamente um problema de chave do cliente. Claro, você quer verificar a configuração do seu cliente também. Mas você fez isso e observou que nada mudou. Isso indica que o problema não é as chaves na sua máquina cliente (e, portanto, a mensagem de erro é enganosa).
Você deve verificar a configuração do servidor.
Por exemplo, descobri que se o seu usuário não for permitido pela configuração do ssh no servidor, o cliente ssh dará exatamente a mesma mensagem de erro (enganosa). Se você não está permitindo todos os usuários, verifique isso:
sudo nano /etc/sshd_config
AllowUsers yourname@*
Verifique também o denyhosts, mas no meu caso o problema era AllowUsers em sshd_config e ele dava essa mesma mensagem de erro enganosa. Corrigir o servidor resolveu o problema sem precisar consertar nenhuma chave no cliente.