We can perform a Galilean transformation and show that:
$$\mathbf{a} = \mathbf{a}'$$
we only need to show that:
$$ \mathbf{F} = \mathbf{F}'=0$$
But this means we have to accept that forces (net force more precisely), don't depend on the frame of reference.
There are a lot of caveats one could make in answering this question. Perhaps most importantly, it is not always true that $\vec F=\vec F'$. For example, if there is a fixed external potential that creates a force then the force is not invariant (unless you also translate the external potential).
However, as long as the force is dependent only on the magnitude of the difference between interacting particles, then it is straightforward to show that $\vec F=\vec F'$.
To convince yourself, have a look at the example of a gravitational interaction force between a swarm of $N$ particles. The force on the $i$th particle in the swarm is:
$$
\vec F^{(i)} = \sum_{j\neq i}^N\frac{-Gm_i m_j(\vec x^{(i)} - \vec x^{(j)})}{|\vec x^{(i)} - \vec x^{(j)}|^3}\;.
$$
Newton's 2nd law for the $i$th particle reads:
$$
m_i \frac{d^2 \vec x^{(i)}}{dt^2}
=
\sum_{j\neq i}^N\frac{-Gm_i m_j(\vec x^{(i)} - \vec x^{(j)})}{|\vec x^{(i)} - \vec x^{(j)}|^3}\;,
$$
where the $\vec x^{(i)}$ represents the coordinates of the $i$th particle in one particular frame.
Now transition to a different frame, related to the first by:
$$
\vec {\tilde x} = \vec x + \vec v_0 t\;.
$$
We have:
$$
m_i\frac{d^2 \vec{\tilde x}^{(i)}}{dt^2}
=
m_i\frac{d^2 \vec{x}^{(i)}}{dt^2}
=
\sum_{j\neq i}^N\frac{-Gm_i m_j(\vec x^{(i)} - \vec x^{(j)})}{|\vec x^{(i)} - \vec x^{(j)}|^3}
=
\sum_{j\neq i}^N\frac{-Gm_i m_j(\vec{\tilde x}^{(i)} -\vec v_0t - \vec{\tilde x}^{(j)} +\vec v_0t)}{|\vec{\tilde x}^{(i)} -\vec v_0t - \vec{\tilde x}^{(j)} + \vec v_0 t|^3}
=
\sum_{j\neq i}^N\frac{-Gm_i m_j(\vec{\tilde x}^{(i)} - \vec{\tilde x}^{(j)} )}{|\vec{\tilde x}^{(i)} - \vec{\tilde x}^{(j)}|^3}\;.
$$
Or, comparing the far LHS with the far RHS of the above equation, we see:
$$
m_i\frac{d^2 \vec{\tilde x}^{(i)}}{dt^2}
=
\sum_{j\neq i}^N\frac{-Gm_i m_j(\vec{\tilde x}^{(i)} - \vec{\tilde x}^{(j)})}{|\vec{\tilde x}^{(i)} - \vec{\tilde x}^{(j)}|^3}\;,
$$
which shows us that the 2nd law has the same form in both frames.
Update:
The example given above of Galilean invariance of the form of the equation of motion obviously also applied to any force that can be written as the gradient of a potential that depends only on the distance between particles.
But, in the comments, a question arose about the existence of velocity dependent forces, such as the Lorentz force. Indeed, considerations of this type eventually lead to the abandonment of the principle of Galilean invariance!
Over 100 years ago, Einstein was curious about a similar issue. He eventually concluded that there is a relativity principle that is different from Galilean relativity that applies to both classical mechanics and classical electrodynamics. This was not immediately obvious, and for a long time many physicists continued to support Galilean relativity along with the postulate of an "ether" that provided a preferred frame for electromagnetism. However, as we all know, eventually Einstein's theory of relativity prevailed.
In Einstein's theory, we no longer have exact Galilean invariance, but rather, the equations of physics are invariant under Lorentz transformations rather than the Galilean transformation.
Update 2
The concept of "inertial frames" is still good and still remains whether we deal with relativistic speeds of not. The thing that Einstein/Lorentz discovered is that we need to use a different transformation to change coordinates from one frame to another.
In non-relativistic mechanics, for relative velocity $v$ much less than the speed of light, we used the Galilean transformation:
$$
t' = t
$$
$$
x' = x - vt
$$
The correct transformation (correct for all relative velocities) is the Lorentz transformation:
$$
t' = \gamma t - v\gamma x/c^2
$$
$$
x' = \gamma x - v \gamma t\;,
$$
where $\gamma = \frac{1}{\sqrt{1-v^2/c^2}}$.
You can show that for $v<<c$ the two transformations are very close to the same, since in this limit $\gamma \to 1$.
