Добавить новую колонку для пароля, например, password_new.
Для пользователей, у которых password_new пустой, но есть старый пароль - при первой успешной авторизации переводить пароль (который нам прислали в POST-форме) в password_hash и очищать поле md5.
Постепенно все активные пользователи начнут использовать новый алгоритм.
Также есть метод с костылями - все существующие md5-хеши перевести в password_hash, а уже при авторизации делать md5 пароля и затем уже проверять с помощью password_verify.
Да, это немного костыли, но решение более простое.
