MySQL large table - querying is very slow

I have a MySQL table, AdsPOI, which has the following structure:

 AdsPOIId  (bigint 20) PRIMARY, AUTO INCREMENT
 Distance  (int 6) not indexed
 poi_POIId (bigint 20) INDEXED, references another table POI
 ads_AdId  (bigint 20) INDEXED, references another table Ads

In this table, currently there are ~7.000.000 rows, but it is growing every minute, larger and larger. The table is an InnoDB table. Even when I try to make the simplest query to the table, for example: SELECT * FROM AdsPOI ORDER BY ads_AdId, the query takes around 20 seconds to run. When I try a more complex query, like SELECT poi_POIId FROM AdsPOI WHERE ads_AdId > 5 AND ads_AdId < 300000 GROUP BY poi_POIId the query takes around 1 minute and 20 seconds, and returns around ~130.000 rows.

Is there any way to fasten these queries? Is it normal, that these queries run so slow? How could I try to make them faster?