I recently spent a lot of time trying to figure out why a private key I exported from putty was not working right on Linux. My issue was I kept getting prompted for a password no matter what.
One clue that may or may not show the issue in the SSHD logs I was NOT seeing "debug1: ssh_rsa_verify: signature correct" when keyed authentication failed and switched to password.
I fixed my problem by deleting the public key in the Linux client .ssh folder. So most likely while copying keys from Windows and putty I must have gotten a mismatch on private/public pair.
If you need it you can re-create it as follow:
rosso@rrosso-VirtualBox:~/.ssh$ ssh-keygen -y -f id_rsa > id_rsa.pub
$ ssh firstname.lastname@example.org
Last login: Sat Nov 7 14:14:08 2015 from 192.168.38.104
Oracle Corporation SunOS 5.11 11.3 September 2015
You have new mail.