Same query on same same table, different response time
For MySQL to handle your query efficiently, you need to create a compound index. Without an index, MySQL must examine every row in your table to count the ones you want. That means it has to read every row from the SSD. That takes time. 

Your filtering criteria are ...

WHERE column_4 = 1 
  AND column_8 is null 
  AND column_3 &gt; CURDATE() - INTERVAL 30 DAY


You need an index that can satisfy your query efficiently. Because two criteria are matches to constant values, those two  columns should come first. Then, the last criterion filters a range of values. Starting with some date in the past it filters records.

So, your index should be on (column_4, column_8, column_3). You create it like this:

 CREATE INDEX tocount ON malicious_table (column_4, column_8, column_3)


You can think of these indexes (they use an indexing technique called BTREE) as lists of data in order. So, the query planner can random-access the index to the first eligible row, and then scan the index sequentially until the last eligible row. That's far more efficient than reading the whole table.

You mentioned your query time is unpredictable. You're right that's unpleasant for your users. It's hard to know exactly why, even for an expert with access to your server. But this general observation applies: If others are using the same server for other things, their operations and yours may interfere with each other in unpredictable ways.  

Pro tip Notice that the index I've given you is designed to match the query you gave. A different query might need a a different index. For example,  if your query were 

  SELECT COUNT(*), MAX(column_13), SUM(column_7)
    FROM malicious_table
   WHERE column_4 = 1 
     AND column_8 is null 
     AND column_3 &gt; CURDATE() - INTERVAL 30 DAY


it would be satisfied with this covering index:

CREATE INDEX tosummarize ON malicious_table 
    (column_4, column_8, column_3, column_7, column_13);


The index I first suggested is made redundant by this index because this one contains the same columns in the same order as that one.

In general, you should avoid creating lots of one-column indexes in hopes of making queries faster. As a database grows, it generally needs indexes to be added (or sometimes dropped) to match the data. The cool thing about indexes is you can add and drop them without affecting your data or programs. Here's a good reference:  https://use-the-index-luke.com/

Edit: Performance variations between queries can be due to many hard-to-discern factors. Is your MySQL server running on a virtual machine on a busy VM host? Does your MySQL server process serve applications other than yours?  How busy is your system? Are lots of other processes INSERTing or UPDATing rows in your table concurrently with your counting queries? If so, the variability may be due to moment-to-moment changes in that concurrent workload. Bluntly, good luck figuring out that one in any detail! You may want to move on to other database performance issues.

There is one thing to try. Precede your counting query with this transaction isolation level setting:

SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;


This reduces the chance that your counting query locks up waiting for other operations on the table to complete. Read this for more details: https://stackoverflow.com/questions/7937472/setting-transaction-isolation-level-of-mysql Your query will still return a useful result, but it might not pick up changes to the table that happen concurrently to your counting request. It is probably acceptable for your application to miss a few most-recent rows in this count. 

And, version 5.6 of MySQL is quite old. It was first released in February 2013. There have been bug and security fixes since, Still, many dozens of years of programmer effort have been spent on later versions since 5.6 came out. Most of them have been spent improving performance and reliability. Upgrade if you can.