Straight to the point - I have a store that had around 30000 products, the url rewrite part of reindexing via shell used to take around 9 minutes (not terrible I know).
I've since deleted around 5000 products and expected to see the reindex take less time. Instead it's had the opposite affect and now the url rewrite part takes 14 minutes plus.
Any ideas why deleting products would cause this?
you can truncate that table and try it and check again.
Hope it will help you.
If work then mark as solution