That's really not the user's responsibility at that point. It's up to the service to store passwords securely (i.e., use proper password hashing functions) and monitor login behavior to throw up extra challenges if things look suspicious.

Password rotation is a high-cost measure placed on the user that has little (even negative) benefit, especially when there are more effective alternatives the service is better-positioned to implement. Users cannot twist themselves into knots to make up for shitty service-side design decisions.