How to prevent usage of leaked keystore and password?

Unfortunately there doesn't seem to be a great way to migrate an existing application to a new signing key. This is probably for the best, since the best practice remains to a) have a strong key and b) keep your private release key as private as possible. I found this article outlining a feasible (but rather user un-friendly way) to migrate from a 1024 bit to a 4096 bit key, which seems to fit your use case. Since you still have a valid signing key for the compromised app, you can attempt to migrate them away from it via update.

1. generate the new signing key, RSA 4096
2. Update the first app, App1, with a mechanism for exporting private data, using TrustedIntents with a signature pin of the new key, RSA 4096, which Checkey will generate for you
3. Create a new version of the app with a different package name, App2
4. sign App2 with new key, RSA 4096
5. Add method to App2 for receiving user data from App1, including a signature pin of the old signing key, RSA 1024, for use with TrustedIntents
6. Publish App2 to the app stores
7. From App1, prompt user to install App2
8. runs and imports data from App1
9. App2 prompts user to uninstall App1

Unfortunately, there is no easy answer to this problem. As mentioned above, the most general solution is to create a new app, tell users to switch, and migrate the data over.

However, on Lollipop+, there is another possible solution. You can use upgrade keys to change the signing key of an app in place, which saves you the trouble of creating a second app or doing the data migration. Unfortunately, Play currently has no support for this, so it's only really an option for off-market apps, and users on Kitkat are out of luck.