Primero, estás seguro que son las consultas? pueba copiando y pengando tus consultas en el phpmyadmin cambiando el número de página (simulando la paginación).
Es raro que tarde tanto, te sugiero que crees indices para los campos
id_categoria
id_linea
id_articulo
pruebalo y comenta que tal te fué
de paso te invito a que pruebes esta
paginación php.
Saludos!