Verifique se a pasta .ssh e os arquivos dentro dela na máquina cliente são legíveis apenas pelo proprietário ( chmod -R 600 .ssh ) e se o proprietário está correto para a pasta e os arquivos (use o comando chown , se necessário) .
Verifique também a pasta e o arquivo authorized_keys no servidor (provavelmente em /root/.ssh ou na pasta inicial do usuário que está tentando fazer login) para garantir que as permissões e o proprietário estejam definidos da mesma maneira.
Editar: com base em mais feedback (e algumas suposições!) - você pode verificar /etc/ssh/sshd_config e ver se o seguinte parâmetro está definido como abaixo. Se não, tente editá-lo.
AuthorizedKeysFile /home/%u/.ssh/authorized_keys
Note que isso pressupõe que você não faça login remotamente como root