Transforming the inequality $(a + b + 1)^2 \ge 0$ yields $a^2 + b^2 + 1 + 2ab + 2a + 2b \ge 0$, from which it follows that $2(ab + a + b) \ge -(a^2 + b^2) - 1$, i.e. $ab + a + b \ge -13$.
The equality is attained if and only if $a + b + 1 = 0$, i.e. $b = -a - 1$. Plugging this into $a^2 + b^2 = 25$ gives us
$$\begin{aligned} a^2 + (-a - 1)^2 &= 25, \\ 2a^2 + 2a + 1 &= 25, \\ a^2 + a - 12 &= 0, \\ (a + 4)(a - 3) &= 0, \end{aligned}$$
hence we get and verify two symmetric solutions: $(a, b) = (-4, 3)$ and $(a, b) = (3, -4)$.