Há duas coisas que eu verificaria.
-
Verifique a propriedade e as permissões da chave privada que você está usando.
-
Verifique o formato da chave ssh que você está usando. Se você estiver usando uma chave SSH ssh comercial, eles terão um formato diferente do OpenSSH (e derivados). Parece-me que você precisará gerar uma nova chave em sua máquina cliente, então você precisará copiar essa chave pública para sua máquina servidora, onde poderá ser necessário convertê-la para uso com o openssh.
ssh-keygen -i -f input.pub > output.pub
Onde input.pub é a chave que você copiou do seu cliente, e output.pub é a chave que você adicionará ao arquivo authorized_keys na máquina do servidor.