Duda con consulta sql desde visual basic

buenos días mis estimados expertos en el tema , pues yo ando con un problemita con una
consulta que tengo en mi código visual basic... Que es esta:
cnn.BeginTrans
If rs1.State = 1 Then rs1.Close
strSQL = "select OPERAC,ESTATUS,PAQUETE from tickets where OPERAC='" & txtClavOp & "' and estatus<>'T' ORDER BY PAQUETE DESC"
rs1.Open strSQL, cnn, adOpenStatic, adLockOptimistic
If rs1.RecordCount > 0 Then

la tabla tickets tiene alrededor de 20 millones de registros, por lo cual la consulta tarda mas de un minuto, uds. Creen que esta en el rango de lo normal? O se puede agilizar la consulta??
cabe recalcar que la tabla el campo operac esta indexado, pues si alguien me puede orientar se los agradezco.
saludos desde mérida yucatán mexico