The point is that the action (or even only the first variation of the action) is invariant. The most elegant way to describe relativistic equations of motion is to use a parameter independent formulation of the action, i.e., a Lagrangian that is a homogeneous function of rank 1 in the (generalized) velocities. For the motion of a massive particle in a vector field the natural choice is
$$A[x]=\int_{t_1}^{t_2} \mathrm{d} t [-m c^2 \sqrt{1-\dot{\vec{x}}^2/c^2}-\frac{q}{c} A_{\mu} \dot{x}^{\mu}].$$
This is the action using the coordinate time ##t## of an inertial frame. Nevertheless this is a scalar action and thus the equations of motion can be forumulated in a manifestly covariant form by introducing an arbitrary scalar parameter which is monotonously increasing with ##t##. The action then reads
$$A[z]=\int_{\lambda_1}^{\lambda_2} \mathrm{d} \lambda \left [-m c^2 \sqrt{\eta_{\mu \nu} \frac{\mathrm{d} x^{\mu}}{\mathrm{d} \lambda} \frac{\mathrm{d} x^{\nu}}{\mathrm{d} \lambda}} - \frac{q}{c} A_{\mu} \frac{\mathrm{d} x^{\mu}}{\mathrm{d} \lambda} \right].$$
The equations of motion leads to those for a charged particle in an electromagnetic field, represented by the four potential ##A^{\mu}##. Note that the variation of the action is also invariant under gauge transformations, i.e., changing the four-potential to ##A_{\mu}'=A_{\mu} + \partial_{\mu} \chi## with an arbitrary scalar field ##\chi## doesn't change the equations of motion, which depend only on the gauge-invariant field-strength tensor ##F_{\mu \nu}=\partial_{\mu} A_{\nu} - \partial_{\nu} A_{\mu}##. All this makes the above Lagrangian a good guess for the correct force law for a charged particle moving in the electromagnetic field, and indeed experiment shows that this is a very good model. It's, however, incomplete since it does not take into account the energy loss by the radiation of electromagnetic waves when a charge is accelerated, but that's another (quite complicated) story.
I am so incapable.