Protect ssh server
Solution 1:
I will try to suggest you another solution for the paranoid:)
http://www.portknocking.org/view/
It works by requiring connection attempts to a series of predefined closed ports. When the correct sequence of port "knocks" (connection attempts) is received, the firewall opens certain port(s) to allow a connection.
And of course only ssh key authentication.