There are many factors that can influence the search speed:
- Database size
- Too many (usually over 8) or poorly programmed plugins
- Server speed
You can learn more about these here: http://wpdreams.gitbooks.io/ajax-search-pro-documentation/content/performance_tuning.html
There are a few ways to fine-tune the search: http://wpdreams.gitbooks.io/ajax-search-pro-documentation/content/performance/fine_tuning_the_search_configuration.html
Plus there is a known issue with WooCommerce (if you are using it). They did something in version 2.3 whereas every plugin that is using ajax is slowed down significantly (about 2-3 more seconds). It's been confirmed by many other plugin developers as well.
We and other developers have already contacted them, but they are refusing to answer or help. Hopefully one of them will respond eventually.
If you like my products, don't forget to rate them on codecanyon :)