Use the "AllowUsers" option in sshd_config to ensure only a small set of users can log in at all. All others will get rejected, even if their username and password are correct.
You can even restrict users to logins from a particular host.
AllowUsers user1 firstname.lastname@example.org
This will reduce the search-space and avoid those old users which have accidentally been left laying around or enabled (although these of course should be disabled anyway, this is an easy way to stop them being used for an SSH-based entry).
This doesn't entirely stop the brute-force attacks, but helps reduce the risk.