If you are receiving the error above, make sure of two things before regenerating the key:
- Your account is not locked on the server
- You are using the right private key!
- You have not added your public key to ~/.ssh/authorized_keys file
- You added the wrong format of public key to authorized_keys file (e.g. added the Putty format instead of the OpenSSH format)
This means that the public key generated by your SSH client was successfully transferred to the server but did not match the one stored on the server. In some cases, as mentioned above, this is misleading. If your account is disabled then you will also get this error on some systems, even if the key you are sending is correct.