Bom, se o processo está muito lento, há varias coisas a serem levadas em consideração…
1. Se essa tabela possui muito índices, cada linha excluída, tem que atualizar todos os índices, isso atrapalha a performance, você pode remover os índices que não estão sendo utilizados no processo e recria-los posteriormente…
2. Você tem certeza que o índice está realmente sendo utilizado ??? Pode ser que, na sua consulta há algum ítem que invalide a utilização do mesmo, verifique primeiro com um select, para ver o tempo de resposta e, se possível, verifique o plano d execução.
3. Pode ser que sua tabela esteja MUITO fragmentada, isso também é um problema na performance…
4. De quanto em quanto você está dando commit no processo, se for de um em um, ai a casa cai… faça de cinco em cinco mil…