This post of ubuntu-tutorials.com (via Planet Ubuntu) suggests to run sshd on a different port than 22.

That does not increase security.

Serious attackers aren't fooled by just changing the port; if someone has an SSH remote exploit we're all in deep trouble anyway (but that code is heavily audited, you bet!), and it's trivial to scan on other ports if a system is detected as being Unix and not having SSH on port 22.

If you want to really increase security, you can

• Disallow password logins altogether, use cryptographic keys or One Time Passwords [wikipedia]
• Enforce (sufficiently) secure passwords
• Filter by source IP from trusted networks only
• Use port knocking [wikipedia]; use iptables RECENT match for this, not some obscure tcpdump-running shell script!
• Require multi-hop or VPN connections (e.g. have a tighly secured firewall host, for example with SELinux, which users can only use to forward their connection to their real destination host)

If your goal actually is to get rid of those annoying (but non-threatening, if you don't have trivial passwords) messages in your log files (you DO read your log files, don't you?) - consider using the iptables RECENT match to stop them early.

At the university, we have a RECENT match filter at the border firewall. It stops SSH scanners early on, giving them 5 tries total for the whole network (and they usually give up after that, not retrying when the recent match has expired).

For some details on how to use the RECENT match for filtering SSH connections, read this earlier blog post on iptables SSH protection. Use the INPUT chain to filter localhost.

For an example how to do a two-hop SSH connection, read this blog post. Just replace his OpenWRT router with a tighly secured SELinux gateway system. Another (without nc) is to use the LocalForward option of ssh. Just forward some local port through one ssh connection to the final machine, then do a second ssh connection over this. The gateway host could easily be restricted to only allow outgoing connections to port 22 in the fenced off network.

So basically, by NOT using a different port than 22 for SSH, you can increase security (by filtering port 22 specially, knowing that it's SSH). If you start putting your SSH daemons on different ports, you're actually making firewalling much harder.

Also note that in some networks, bandwidth policies are used for different ports. The SSH port usually is not limited; arbitrary ports are (since it might be a filesharing application using them). Another reason to stick to the standard ports, so you don't get punished by your network administrators!