Если база относительно средних размеров, наверное проще перегнать данные в новую базу аналогичной структуры, где вообще отсутствует ссылочная целостность, identity и индексы. Затем обновить ключи и затем накатить структуру. На личном опыте - redgate в плане структуры позволяет всё быстро сделать
Базы у нескольких клиентов, структуры одинаковые, но подключение удалённое и по времени желательно побыстрее соответственно завершить этот удаленный сеанс)
Думаю, в моем случае, проще написать скрипт на создание поля, где задам ему значения от 1 , удалить старое, сделать новое Identity и заменить имя у нового на то которое было у старого. Надеюсь, удалить такое поле, которое Identity, можно. Именно это поле не ключ ни для кого и неважно какое значения были, важно чтобы стали с 1.