I took several steps in securing my servers:
The first is the obvious one:
Don't run ssh on a standard port gets you rid of the usual skript kiddies attacks.
The second one is also state - of -art:
Use a knock - daemon. A knock - daemon first awaits a sequence of hits on specific ports and protocols before opening the port for the ssh - connection on the server.
So the ssh - server is invisible to any attackers until they hit the right port sequence with a knock client. Most knock - daemon - implementations provide a mechanism for integrating transactional sequences, so the knocking sequence is changed after every successful login.
With this standard setup you are provided with a bit more of a security layer.
Using encrypted usernames and passwords and restricting ssh - login to a specific (non - root) user is also recommended. You can then switch to the root user on the server when executing root tasks.
Installing a monitoring system like nagios also provides more security to you and your environment, it's easy to configure and also provided through the ubuntu packaging system.
You can configure it to send you emails when someone is logging into your server via ssh, so at least you will get the information you need to take some further investigations.
But, to be honest: If someone accessed your server as root, you should do a complete re-installation of everything. There could be replacements of binaries which are not easy to detect, introducing backdoors. Imagine you run a simple command like useradd and the binaries have been replaced so that while executing the command a tcp connection is opened and user credentials are send to your intruder. Or, worse: The ssh - server binary has been replaced with a customized version which allows access via a certain user - pass - combination.