In fact, "Admin" > "Stats" > "Reindex content" is slow. The reason will be that only 10 posts are processed per one Ajax request. Your server seems to have sufficient performance. Therefore, if your server (PHP and MySQL) has sufficient resources (settings), you may be able to speed up by increasing this processing count.
Hacking example of reindex count per one ajax request:
Source: qa-include/app/recalc.php around L133 in case of V1.8
Code:
case 'doreindexcontent_postreindex':
//$posts=qa_db_posts_get_for_reindexing($next, 10);
$posts=qa_db_posts_get_for_reindexing($next, 100);
Note:
This process consumes a lot of server resources. Especially in case of shared server, you need to be careful. And, this change does not always work correctly on your server. It is important to gradually increase the value. For example, 50 > 100 > 300 ...