Well, apparently with Zmap [1] you can do internet-wide scans in less than an hour from a single host, so I can't imagine they'd have that much trouble finding any open SSH ports on a smaller IP range.
So just changing the SSH port will do little, but enabling port knocking would help it stay hidden.