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.
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 try to authenticate, and when it fails, look for log file:
/var/log/secure
It will have errors you are looking for.