Encryption at Rest Migrations

What should I do to move away from a weak encryption algorithms in my database or storage?

In order and without skipping or re-arranging steps:

1. Add another field for the new version;
2. Write to both fields;
3. Optimistically read from the new field if populated and not the old field;
4. Asynchronously re-encrypt everything;
5. Read only from the new field;
6. Remove the code that reads from the old field;
7. Backup if deemed appropriate and drop the old field.