I've had this problem for more than 2 years now and I can confirm it's a problem in the database of contacts storage when you have so many contacts (thousands). Although the initial sync of contacts might take like few minutes to grab all the contacts from Google server to your phone, it takes "DAYS" for the database structure to finalize the optimization process of such big amount of contacts.
Solution#1: Disable Sync of Contacts and restart your phone. This will make it run smooth, but if you need to update your contacts from/to the server you have to enable Sync again.
Solution#2: Be patient for few days until the Contacts Storage database reaches its steady state. Keep monitoring daily the file size of "Contacts Storage" using any app manager, as long as the size keep growing then the process of database optimization is still ongoing.