I realize this is an old post, but I had the exact same problem with an Ubuntu server. I had 'PasswordAuthentication no' and 'PubKeyAuthentication yes' in my sshd_config and I was able to connect to the server with my private key, but the moment I tried to connect to the database with my MySQL client using the same key, it would always fail. For me the solution was to generate a new SSH key with PuttyGen. In the top menu, go to 'Key' and 'Parameters for saving key file'. Ensure the ppk version is 2 and not 3, and choose ECDSA as the key type.

Hopefully this helps you or someone else that comes across this post.