I have 4,000 contacts. Very often but not always I find searching for a name taking a few minutes! When the name is found and I choose it, it could take a minute or two display the content. Even looking for the details of a Favourite contact could take more than a minute to retrieve the content. How come? Maybe it is going out to the Internet because some of the records are linked to Exchange and LinkedIn. So, how can I speed things up? Do I have to stop sunc-ing contact databases in the cloud to my phone?
Welcome to Android Central! Which phone do you have? My wife's HTC One M8 had this issue, and it was resolved by going to Settings>Accounts, removing her Google account, then adding it back again. She has 5000-6000 contacts, so I think this can happen with big numbers. I also noted that her Google Contacts sync would sometimes seem to get stuck syncing forever. She has lots of LinkedIn contacts as well. Once I removed her Google account and added it back, the problems resolved.