TL;DR: use xt_recent to allow persistent clients rather than block them.The xt_recent (formerly ipt_recent) module for iptables is well known as a way to limit a malicious attacker's ability to brute force your exposed SSH server. Just do a google search for iptables brute force for examples. All of these are reactionary, meaning they only start limiting connection attempts only after a certain number of successful TCP handshakes.
There are user-space programs that are more or less equivalent. Fail2ban, in particular, watches the auth.log for failed logins, meaning it's not rate limiting raw TCP connections, but rather actual login failures, which is likely what you're really after anyway. It's still reactionary, not blocking the IP until someone has had a go at it for a while.
I prefer something more proactive, and was looking at various flavors of port-knocking to meet my needs. They too come in kernel and user space forms, but the kernel solution using xt_recent was way too complicated, in my opinion, involving several states and chains. Plus, all the solutions require either a separate client or some other way of preceding your real connection attempt with the knock sequence.
Then it hit me.
Why not have the knock sequence just be a few extra knocks on the same port as the service?
Port scanners and brute force tools generally only send a single SYN packet. If they don't get a response, they assume the port is filtered and move on. Yet TCP is a reliable protocol. If a client with a full TCP stack sends a SYN and doesn't get a response, it sends another. Then another, and another. While the wait between retries backs off between each attempt, within the first 4-5 seconds, I can reasonably expect the client to have sent 4 identical packets.
With this knowledge in hand, I tested a firewall ruleset which very effectively blocks most port scanners and brute forcers, but lets real clients in with only a 3-4 second delay on each connection attempt. I call it "knocking harder."
Since I primarily use UFW on Ubuntu 12.04.5, I have edited the /etc/ufw/after.rules file with the following patch. I put this in after.rules so that the normal user rules can still be used to whitelist or blacklist by source IP (eg. I don't want to have to "knock harder" from certain hosts, or I want to block certain bad IPs that resend SYNs). Plus, it should still play nice with fail2ban, if you'd like to actively ban IPs with a series of failed service logons.
I've tested with the OpenSSH client on OS X and Ubuntu (12.04.5 and 14.04.1) as well as PuTTY on Windows 7. It does delay the connection establishment by 3-4 seconds, but if you're using SSH multiplexing, that's only on the first concurrent connection.
In the short time it's been active, I have not seen any sources other than mine actually make it through iptables to the sshd service. Even the IPs that were previously attempting to brute force me have been stopped. As far as they know, I've taken the service offline or blocked their IP.
It's as close to an ideal solution as I've found for balancing between invisibility, complexity, and availability.