Laravel 4 Pagination method

I have a web app built in Laravel 4, I have a clients table in the database with more than 20000 records, everything working fine, but my hosting service told me that I need to improve my query to retrieve the clients data. I'm a little confused about this issue, I'm not sure what is wrong or how can I improve my query.

$data = Client::orderBy('created_at', 'desc')->paginate(50);

How is the best practice to retrieve data from a table with thousands records?

Thanks in advance!