Putty: Getting Server refused our key Error
Adding a few thoughts as other answers helped, but were not exact fit.
First of all, as mentioned in accepted answer, edit
/etc/ssh/sshd_config
and set log level:
LogLevel DEBUG3
Then restart sshd
on the server to have it use the changed log level, e.g.:
sudo service ssh restart
Then try to authenticate, and when it fails, look for log file:
/var/log/secure
It will have errors you are looking for.
OK, there was a small typo in my key. Apparently when pasting to file the first letter was cut off and it started with sh-rsa instead of ssh-rsa.
nrathathaus - your answer was very helpful, thanks a lot, this answer is credited to you :) I did like you said and set this in sshd_conf:
LogLevel DEBUG3
By looking at the logs I realized that sshd reads the key correctly but rejects it because of the incorrect identifier.