Can I use SSH key authentication to log into a remote system with a different username?

Yes, you can do this, just as you described it.

baruser@here ~$ ssh-add -l
4096 10:b3:fd:29:08:86:24:a6:da:0a:dd:c6:1e:b0:66:6a id_rsa (RSA)
baruser@here ~$ ssh foouser@remotesystem
motd message, etc.
foouser@remotesystem ~$

It's a bit of an aside, but.....

If you're always using the same username for a remote server, you may also find it useful to add a host into your ssh config:

Host remotesystem
    User baruser

That way you don't need to remember to specify user name when logging in, and you rule that out when having issues with keys in future.

Your local username doesn't really matter (aside from the private key having to reside inside your local user's home directory). Just copy the key to the remote user's authorized_keys section and it will work.

The permissions on the .ssh directories on both machines much be correct. Generally, that means 700 on the .ssh directory and at most 755 on the home directory. In addition to 600 on all the files in the .ssh directories.

If the user on the remote system is root, make sure that root can ssh. (PermitRootLogin in sshd_config) and that public key (PubkeyAuthentication) and if necessary RSA (RSAAuthentication) are enabled.

With any ssh related problems, the first thing to do is turn up the client verbosity:

ssh user@machine -vvv

If this fails to give you any insights as to what is wrong, you need to change the log level on the server and restart the daemon.

LogLevel DEBUG3

You should find the debug output in /var/log/auth.log (or where ever ssh is configured to log to). Once you've found the problem, remember to set it back to how you found it.