Would it have helped if the authorized_keys file contained hashed versions of the public key? As far as I recall it worked that way when using SSH protocol version 1.