There are good ways to prevent getting rooted, as you say, but I know exactly what you mean. The first time I set up a virtual server, someone began a dedicated brute-force, dictionary attack against ssh within 30 minutes. The attack wasn't particularly aimed at me, of course, since I had an empty virtual machine on an ip number that I had been given only a half hour earlier. Still, it's a bizarre thing to watch the logs and see some machine hammering at your door (even if you believe the door to be very solid). The attack went on for over 12 hours, for whatever that's worth. It felt damn scary the first time - even though I knew that I had absolutely nothing of consequence in the server yet (brand-spanking new) and that I could wipe the whole setup and start fresh with nearly zero effort. Nevertheless, it was creepy. It's sort of like being in a horror movie: you simply watch and listen as the monster pounds on the door. (Of course, you have a lot more options than the twits in the movies, and your monster is usually either (1) a pimply-faced kid in suburbia or (2) a cyber-criminal who doesn't much care where he gets in and happily moves onto the next ip in short order. But the initial
feeling was like that.)
Like most of the other posters, I ended up taking the following steps to cut down on the problem: (1) disable root login at all, (2) switch sshd from port 22 to another, random port for listening (that alone cut the attacks way, way down), (3) disable all password based logins; only key-based logins work now, (4) limit the users who could login remotely at all to a very small group (you can create a group just for this purpose, enroll two or three admins and edit your sshd_config file to allow only members of that group to login at all), (5) use rate-limiting in iptables to freeze out any attacking ip after two or three failed attempts in a minute.
A link with lots of detailed methods to handle brute force attacks and their pros and cons, in case anybody wants it: http://la-samhna.de/library/brutessh.html