Could be depending on the type of key or SSH client used, especially if the key and/or client is very old and/or defective (there were compromised / blacklisted keys because of a bad RNG). The defaults for key security are ever increased with newer OpenSSH releases. That is, bad or insecure mechanisms are slowly thrown out.
Try to create new SSH keys with a modern client, install the public key an try if that works.
Try to create new SSH keys with a modern client, install the public key an try if that works.
"