Wow you're right. I just setup my own VPS yesterday. Decided to check the auth logs and the first invalid user attempt occurred less than 3 hours from my first login.
The "POSSIBLE BREAK-IN ATTEMPT!" message worried me for a bit but a little googling and the fact I've disabled password login calmed me down.
Presumably, changing my sshd port will drastically reduce these attempts right? Or do attackers routinely port scan servers?