Password Migrations

Follow similar steps to the database field migration, use a new field and choose a proper hard password algorithm. Check out Argon2, or use libsodium's password hashing. Avoid introducing bcrypt as it truncates the password length. Consider a migration window of one year. For the "asynchronously re-encrypt everything", use the authentication event from users as a lazy opportunity to upgrade their credential fingerprint. After that any time an account tries to log in with an existing but un-migrated user regardless of password input, respond in the application as if the credential were incorrect and communicate to the user outside the application that they must reset their password.

While I consider it unclean, you might try a two-phase migration where you use a password hard algorithm (e.g. argon2 or scrypt) on the MD5 value and then flag the user for upgrading to the second phase when they present their credential. That way at least if your database is dumped in the mean time, it won't be as useful to an adversary. I have seen this happen over the course of a two year migration and it worked with zero frustration for returning users.