This is not possible without some serious code changes to sudo and sshd. Sudo doesn't know about login methods, and ssh doesn't publish to other programs anything that would indicate whether public key, password, or some other mechanism was used for login.
As someone else said, you can use the NOPASSWD option in sudoers - this would apply to specified users always, though, not only when they use ssh with private keys.
If you really want, there may be tricks you can do with a suid program that checks the sshd log and locks/edits the sudoers file to let that user do a no-password sudo, and a periodic task to revoke this permission.
All that said, I think this is a bad idea. Requiring a password for privileged commands has a couple of nice benefits that private key SSH doesn't. Notably, it lets you have timeouts for the auth (password must be re-entered, not true for ssh sessions), it lets you have password minimums and rotation (unlike ssh keys, which have a passphrase outside the server's control).
http://askubuntu.com/a/135838 If you put those users into a group, you sure can! – Rob – 2012-10-24T21:07:45.677
try
sudo visudo
and change your password toNOPASSWD: ALL
see if that works – pneumatics – 2012-10-24T21:08:15.1903@AlanTuring That would also work for users in that group who identified via a password. – Xyon – 2012-10-24T21:27:26.960
@AlanTuring That would effectively decrease the security of the server - I want only certain users, not all, sudo – Mikko Ohtamaa – 2012-10-24T22:14:13.613
It's possible to give priviliges to specific users. See my answer. – Isaac Rabinovitch – 2012-10-26T08:21:43.410