Verifique as permissões no sistema remoto:
$ chmod 700 ~/.ssh
$ chmod 600 ~/.ssh/authorized_keys
Existe uma ferramenta que pode ser instalada em seu dist (ubuntu / debian) chamada: ssh-copy-id que fará isso para você:
$ ssh-copy-id <remote>
Se isso não funcionar, tente ssh com a opção "-v" para ver mais mensagens detalhadas.
Versão longa:
#From client to server
client$ scp ~/.ssh/id_rsa.pub remote_server.org:
# next, setup the public key on server
server$ mkdir ~/.ssh
server$ chmod 700 ~/.ssh
server$ cat ~/id_rsa.pub >> ~/.ssh/authorized_keys
server$ chmod 600 ~/.ssh/authorized_keys
server$ rm ~/id_rsa.pub