In most cases I've seen earlier the problem is related to improper PuTTY configuration, rather than problems on the server side.
Try to take some Linux machine with the shell access, generate SSH key, put it to Plesk (via SSH keys manager) and check the ability to connect using keys. This action should help to localise the problem (server or client side configuration is not ok).