There are some very simple steps you can take to really harden remote access over SSH, especially if you can't simply tie the service down to a limited number of source ports.
First things first, sshd_config. In Ubuntu this is usually found in /etc/ssh and can be used to configure a great number of features. The simplest ones to deal with are always the best. Restricting the users who can login via SSH is a first principle. This can be done in one of two ways, by user or by group. AllowGroups allows any user in this group authenticated access to the server via SSH. A more fine grained approach is to use the AllowUsers option.
Another easy win is by moving the listen port from 22 to some other randomly assigned port. This reduces the likelihood of a scan showing SSHD running.
Other steps you might want to take include disabling root access, disable password authentication and using keys only.
The next step is a wee tool called Denyhosts (http://denyhosts.sourceforge.net/). Make sure you've got the additional sources enabled in /etc/apt/source.list and then type:
sudo apt-get update
sudo apt-get install denyhosts
DenyHosts is a python script intended to be run by Linux system administrators to help thwart SSH server attacks (also known as dictionary based attacks and brute force attacks).
Denyhosts acts as a dynamic blocker for SSH and other services. It relies on the /etc/hosts.deny and hosts.allow. It dynamically builds a list of hosts that repeatedly connect to your server. By default the service will block connections from IP sources that are repeated attempting to connect and access your host. The denyhosts process is configured in /etc/denyhosts.conf
There are additional things that can be done using iptables to rate limit connections and you should always run a firewall on your hosts but I'll deal with that in a separate post.
Once you've put these steps in place you can rest assured the SSH on a public facing host is much more secure, there's no guarantees but every little helps.