That ssh log message indicates they accessed using your public key. How on earth did they get that? Did you access from some other systems that they may have also got access to? This is pretty common. This means you need to check all other computers that previously you used to connect to your laptop. A public key is not more safe than a password if it's left laying around on various systems.
People often use a key for automated access (scripts etc). If you do that it should be for a different, limited user that can only do the very limited functions you intent to automate.
I don't understand it either, apparently they got first into my home machine (with password auth enabled), grabbed the private key for my work machine and logged in there. No idea as to how.
Any possibility of physical access at home? Roommate, neighbor, wandering gypsy, anyone who has physical access can gain root without password and then access your key - unless you use encrypted home or an encrypted hard disk.
Do you have remote access methods open at home, eg. VNC, or run a web server or other service? These are things that can get compromised. Java based web apps/servers seem to be open like swiss-cheese nowadays going by reading the news anyway.
Even someone with brief access to your laptop could simply run ssh-copy-id to some remote server they control. That would give your key to their server for later re-access. I wouldn't fully believe this was a Russian user. It could just as easily be your next door neighbor using a proxy.Check whether an additional key has been added to your laptop's ~/.ssh/authorized_keys file. This could be done by anyone with even a few moments access to your laptop.
Another thing I noticed - your sshd log msg indicates the user used sftp to login since it happened at the same exact same second as the ssh login. Hence, it wasn't a user logging in to the console and then choosing to use sftp. Have there been machines where you used sftp to view files? This uses ssh as a transport layer but you may have thought differently about how you connected since the client would not be console but Nautilus or any number of file browser apps.