We claim that the answer is 12. We first show that if 13 squares are colored red, then some four form an axis-parallel rectangle. Note that we can swap both columns and rows without affecting whether four squares form a rectangle, so we may assume without loss of generality that the top row has the most red squares colored; suppose it has $k$ squares colored. We may further suppose that, without loss of generality, these $k$ red squares are the first $k$ squares in the top row from the left. Consider the $k \times 5$ rectangle formed by the first $k$ columns. In this rectangle, no more than 1 square per row can be red (excluding the top one), so there are a maximum of $k+4$ squares colored red. In the remaining $(5-k) \times 5$ rectangle, at most $4(5-k)$ squares are colored red (as the top row of this rectangle has no red squares), so there are a maximum of $(k+4)+4(5-k)=24-3 k$ squares colored red in the $5 \times 5$ grid. By assumption, at least 13 squares are colored red, so we have $13 \leq 24-3 k \Longleftrightarrow k \leq 3$. Hence there are at most 3 red squares in any row. As there are at least 13 squares colored red, this implies that at least 3 rows have 3 red squares colored. Consider the $3 \times 5$ rectangle formed by these three rows. Suppose without loss of generality that the leftmost three squares in the top row are colored red, which forces the rightmost three squares in the second row to be colored red. But then, by the Pigeonhole Principle, some 2 of the 3 leftmost squares or some 2 of the 3 rightmost squares in the bottom row will be colored red, leading to an axis-parallel rectangle - a contradiction. Hence there are most 12 squares colored red. It remains to show that there exists some coloring where exactly 12 squares are colored red, one example of which is illustrated below: \begin{tabular}{|c|c|c|c|c|} \hline & R & R & R & R \\ \hline R & R & & & \\ \hline R & & R & & \\ \hline R & & & R & \\ \hline R & & & & R \\ \hline \end{tabular} The maximum number of red squares, therefore, is 12.