The first step to getting out of the local permissions / server login catch-22 is to know you're in it.
Perhaps you found this page searching for "Permission denied on publickey even though I can log into the server with a public key it doesn't make any sense grrr argh how dare it deny me i created it why won't it work permissions are correct this isn't right" or something like that.
Your problem is that when you run the command without sudo, you don't have the proper permissions locally, and your computer doesn't even try to connect to the server:
Except where otherwise noted, content on this site is licensed under a Creative Commons Attribution 3.0 Unported License.