This post can probably help someone because it's not documented anywhere or can't be found on google. (before I wrote on google)
Whenever there is an error like this, it's said to check that we have
RSAAuthentication yes PubkeyAuthentication yes
in sshd_config & have proper permissions in the .ssh directory.
chmod 700 ~/.ssh/ chmod 600 ~/.ssh/*
But, it wasn't helping me in any way. As a convention, I had saved the public keys with the name "~/.ssh/authorized_keys2" while I also had the option below enabled which was preventing the required file from being processed.
# The default is to check both .ssh/authorized_keys and .ssh/authorized_keys2 # but this is overridden so installations will only check .ssh/authorized_keys AuthorizedKeysFile .ssh/authorized_keys
Silly me, but it took a bit of time to figure this out. Hope it will help someone.