consulta con limit es muy lenta

[primary]

Hola primero comentar que no tengo ningún filtro que añadir solo el de eliminado y no tiene indice.Respecto a la lentitud la consulta con limit 0,200 me tarda 0.09s con limit 99000,200 me tarda 2.8s para mi es lento.No se que opinais?
Respecto a gnzsoloyo ante todo gracias por tu ayuda y comentarte.La tabla no tendrá más de 100.000 registros en este caso no tengo alternativa o lo dejo así o no creo paginador o no lo hago efectivo.No entiendo muy bien que hacer en un caso así?
Vi por Internet un truco como hacer un select dentro de otro selectivo con join donde el select segundo obtiene los id del rango y luego con join muestra los registros igual al id la verdad que mejora la consulta pero al aplicarle el filtro eliminados=no en el segundo select de la consulta esta se hace aún más lenta.
No se sigo muy indeciso de que puedo hacer.
Saludos.