The optimization process and recommendations:

1. Avoid Selecting Unnecessary Columns (query line: 2): Avoid selecting all columns with the '*' wildcard, unless you intend to use them all. Selecting redundant columns may result in unnecessary performance degradation.
2. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.
3. Replace In Subquery With Correlated Exists (modified query below): In many cases, an EXISTS subquery with a correlated condition will perform better than a non correlated IN subquery.

Optimal indexes for this query:

ALTER TABLE `orders_status_history` ADD INDEX `orders_history_idx_orders_id_orders_id` (`orders_id`,`orders_status_id`);

The optimized query:

SELECT
        * 
    FROM
        orders_status_history 
    WHERE
        NOT EXISTS (
            SELECT
                1 
            FROM
                orders_status_history AS orders_status_history1 
            WHERE
                (
                    orders_status_history1.orders_status_id = 3
                ) 
                AND (
                    orders_status_history.orders_id = orders_status_history1.orders_id
                )
        )