Laravel slow simple query with Eloquent

I have a problem with a query with laravel, I have a database with 250k records called orders

When I try to get a paginated orders by client_id, I get 504 time out.

The query is very simple.

$ordenes = Order::where('client_id', $id)->orderBy('id', 'desc')->paginate(20);

My temporary solution was increment from 1gb RAM to 2gb and 1cpu to 2cpu's. But I want to know if it's posible optimize this simple query to get a faster response.

via Chebli Mohamed