Зачем же удалять? Проанализировать все надо, какие индексы добавить, а какие может и ненужны. Можно посмотреть статистику и фрагментацию индексов. Сильно фрагментированные индексы перестроить. Кстати, для фрагментированных индексов при переиндексировании можно fill factor поменьше сделать (только надо помнить, что это чревато лишним местом на диске), тогда фрагментироваться не так быстро будут.
Да кстати, не знаю как переиндексация на большых таблицах (я с такими не сталкивался), а вот создание индекса занимает немало времени (у меня на таблице в 1500000 записей порядка 4-5 минут), от железа зависит, конечно и его загрузки.

Я бы посоведовал вначале проанализировать все, а потом когда сервер загружен меньше всего провести работу.
Удачи