The sproc's execution time can vary - if DB maintenance hasn't been performed, then reindexing could take quite some time. It is also highly dependant on your machine's hardware.
For the forum related sprocs, if you're still having issues after the rebuild, try adding the following index.
CREATE INDEX IX_te_Forum_ThreadReplies_ParentReplyId ON te_Forum_ThreadReplies (ParentReplyId)
This was a missing index we discovered in 7.6 in bug #33348. This was fixed in 8.0, and whilst it hasn't been backported into our 7.6 hotfix branch, We have provided this index to a number of customers on 7.x with very large forums and had a lot of success.