What could cause remote drush commands to fail with ssh errors when ssh works in all other cases?
Put this line in your drushrc.php file:

$options['ssh-options'] = '-o PasswordAuthentication=no -i /home/YOURUSERNAME/.ssh/id_rsa';


This will cause Drush to pass these options along to ssh any time it calls your remote system, so you can continue to call Drush via sudo, and still use your login user credentials.