Improve SQL queries speed

I'm using MySQL and i have schema like:

|------------|-------------|------------|--------------|
|    cities  |category_city|  categories|   companies  |
|------------|-------------|------------|--------------|
|     id     |  city_id    |     id     |     id       |
|    name    | category_id |    name    |subcategory_id|
|            |             |  parent_id |    city_id   |
|            |             |            |...other cols |
|____________|_____________|____________|______________|

Relationships: City with Category has ->belongsToMany()

public function categories()
{
    return $this->belongsToMany(Category::class);
}

Categories has subcategories:

public function subcategories()
{
    return $this->hasMany(Category::class, 'parent_id', 'id');
}

And i'm getting companies from category and filtering by city, because i need the current city companies and for that i have a global scope:

 public function getCompanies($city_id)
    {
        return $this->companies()->whereHas('mainCity', function ($q) use ($city_id) {
            $q->where('city_id', $city_id);
        });
    }

mainCity method:

public function mainCity()
{
    return $this->belongsTo(City::class, 'city_id');
}

Here is my method performing the query with AJAX request:

public function getPlaces(City $city, Category $subcategory, $north, $south, $east, $west)
{
    $companies = $subcategory->companies()
        ->withCount('comments')
        ->companiesByBounds($north, $south, $east, $west)
        ->paginate(8);

    $markers = $subcategory->companies()
        ->companiesByBounds($north, $south, $east, $west)
        ->get(['lat', 'lng', 'slug', 'title']);

    return response()->json(['companies' => $companies, 'markers' => $markers], 200, [], JSON_NUMERIC_CHECK);
}

In companies i have ~2m records. The main problem is that the queries taking 3.5 seconds. Help please to improve my queries.

via Chebli Mohamed