It's probably not related to the actual search process, but either a post process step or additional processes running with the ajax request.
In WordPress when an ajax request is executed first WordPress core is initialized, then it loads every plugin cores then goes through the list of the registered ajax handlers. The problem usually is caused at the step where the plugins get initialized. Some plugins check at the beginning of their execution if the current call is within an ajax request, and only load the absolutely necessary codebase – but most of them not. This can cause a huge delay.
The sysbench looks all right to me, but it does not mean that there shouldn't be any hold-ups within ajax requests.
Please check out the Performance Tracker section of the documentation. I've built in a basic process measurement tool to the plugin to check how long the search process actually takes. If the Average Request Runtime is considerable lower than the actual response on the front-end, then it means that something else is clogging up the ajax request. (wordpress core loading, plugin loading and code execution etc..)
There is also a chapter about Fine Tuning the search Performance, where you should find a few tips about performance related improvements.
If the Average Request Runtime is high on the performance tracker, then let me know. If you can work out an FTP access, I will gladly do a debugging to find which part is actually causing the delay.Best,
If you like my products, don't forget to rate them on codecanyon :)