Parece que o servidor está executando no SSH v2 em vez do OpenSSH, que é o formato em que a chave pública SSH está.
Devido a esse problema, o servidor não consegue lidar com a leitura e a negociação da chave pública de maneira que faça sentido para tudo. Essencialmente, isso é como inserir uma senha e digitá-la como inglês quando o servidor esperava que fosse em grego.
Portanto, para corrigir isso, precisamos converter a chave OpenSSH em uma chave SSHv2 (também conhecida como RFC4716). O OpenSSH fornece um comando para fazer isso:
ssh-keygen -e -f /path/to/openssh/public/key > /path/you/want/the/rfc4716/key
Execute isto e pegue a saída e faça o upload para o servidor, se as chaves ainda não tiverem sido convertidas no servidor.