Hi
Can you let us know the version of Alfresco version you are using?
Is this search as a regular user?
How are you doing the search?
What is the search string?
Try limiting the number of results returned by the query.
This is done in the UI search and available on the search API.
This will reduce the number of underlying operations (like access checks) on nodes you will never display - just to see how many things you would find.
I suspect you are finding all or nearly all docs and doing access checks on all of them.
Regards
Andy