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.