Options for dealing with sshd brute force attacks

Hi,

We all know that public facing ssh servers will get tons of brute force 
attacks. That's just a fact of life.

For many machines, running blocklistd helps tremendously. But what happens 
when blocklistd won't help because npf can't be used?

OpenSSH doesn't use tcpwrappers any longer, but I suppose I could launch 
it from inetd as one option.

One machine has had more than 300,000 attempted logins in the last twenty 
hours. Password based authentication is off, so I'm not worried about 
anyone getting in, but it's making logging in difficult due to MaxStartups 
and it's noticeably raising the load of the machine.

What would people recommend here?

Thanks,
John