The password for the client machine changes every 15 days, so we can't use ssh public keys.

The changing of the password should have no bearing at all on your ability to use keys for auth. Could you explain further?