...There are around 3.5 Lakhs records in my GenericAttribute table.
... take around 30 second to get result for 1st time.
... take around 30 second to get result for 1st time.
350K is not that much. Maybe your SQL Server is slow. Is it on the same server as your Web Site? (not a good idea)
Look at results of these queries, and compare to number of your actual / real customers. (Maybe you are not properly 'deleting' all the guests / spammy customers. Note that using "Delete" in the admin customer page only sets the Deleted column on the Customer record, and does not really remove customer or their linked records.)
SELECT count(distinct EntityId)
FROM [GenericAttribute]
WHERE KeyGroup = 'Customer'
SELECT [Key], Count(1) as Count, Count(distinct EntityId) as CountCustomers
FROM [GenericAttribute]
WHERE KeyGroup = 'Customer'
GROUP BY [Key]