The point is not so much relativistic vs. non-relativistic dynamics but gauge invariance, but it's of course most elegant to argue for the Lagrangian using relativistic arguments, because electromagnetism is a relativistic theory since Maxwell discovered it although it took about 40 years to fully understand this in Einstein's famous paper of 1905.
The first observation is that to write down manifestly covariant consistent equations of motion for a point particle in relstivistic physics it's most easy to parametrize the worldline of the particle in Minkowski space and then deriving these equations of motion from the Hamilton variational principle. The most simple argument is to aim for an action which is (a) Poincare invariant and (b) invariant under reparametrizations of the worldline.
For the latter demand it's obviously sufficient to make the Lagrangian a first-order homegeneous function in the ##\dot{x}^{\mu}##, where the dot refers to the derivative with respect to the arbitrary world-line parameter, ##\lambda##, i.e., we demand that
$$L(x,\alpha \dot{x})=\alpha L(x,\dot{x}),$$
because then the action
$$S[x]=\int_{\lambda_1}^{\lambda_2} \mathrm{d} \lambda L(x,\dot{x})$$
is invariant under arbitrary reparametrizations ##\lambda \rightarrow \lambda'## since we have
$$\mathrm{d}_{\lambda} x^{\mu} = \frac{\mathrm{d} \lambda'}{\mathrm{d} \lambda} \mathrm{d}_{\lambda'} x=\alpha \mathrm{d}_{\lambda'} x$$
On the other hand
$$\mathrm{d} \lambda = \mathrm{d} \lambda' \frac{\mathrm{d} \lambda}{\mathrm{d} \lambda'}=\mathrm{d} \lambda'/\alpha.$$
So you get
$$A[x]=\int_{\lambda_1'}^{\lambda_2'} \mathrm{d} \lambda' \frac{1}{\alpha} L[x(\lambda'), \alpha \mathrm{d}_{\lambda' x}(\lambda)] = \int_{\lambda_1'}^{\lambda_2'} \mathrm{d} \lambda' L[x(\lambda'),\mathrm{d}_{\lambda'} x(\lambda')].$$
For the free particle from translation invariance in time and space you get
$$L_0=L_0(\dot{x}).$$
Then the only Lorentz invariant quantity homogeneous in first order in ##\dot{x}## is ##\sqrt{\dot{x} \cdot \dot{x}}##, i.e.,
$$L_0=C \sqrt{\dot{x} \cdot \dot{x}}.$$
Choosing the coordinate time as parameter, as is usual in Newtonian physics, you get
$$L_0=C \sqrt{c^2-\mathrm{d}_t \vec{x}^2}=C c \sqrt{1-\beta^2}.$$
The non-relativistic limit follows for ##\beta \rightarrow 0##,
$$L_0=C c (1-\beta^2/2)=C c[1-v^2/(2c^2)].$$
In order to get the right free-particle Newtonian limit, ##L_0=m v^2/2 + \text{const}## you must choose ##C=-mc##, i.e.,
$$L_0=-m c^2 \sqrt{1-\beta^2} = - m c \sqrt{c^2-v^2} = -m c \sqrt{(\mathrm{d}_t x) \cdot \mathrm{d}_t x)}.$$
Since now the action is parametrization invariant by construction, this holds for any parametrization of the world line, i.e.,
$$L_0=-m c \sqrt{\dot{x} \cdot \dot{x}}.$$
Further we know that the electromagnetic field can be derived from a four-potential,
$$F_{\mu \nu}=\partial_{\mu} A_{\nu}-\partial_{\nu} A_{\mu}.$$
The most simple interaction Lagrangian with a four-vector field and homogeneous in first order in ##\dot{x}## obviously is
$$L_{\text{int}}=C \dot{x} \cdot A.$$
It turns out that you get the correct relativistic version of the Lorentz force by choosing ##C=-q/c## (in Heaviside-Lorentz units), i.e.,
$$L_{\text{int}}=-\frac{q}{c} \dot{x} \cdot A.$$
Now it is also important to note that we must get a gauge invariant action since the physics is not described by the four-potential, ##A## but by the four-potential modulo an arbitrary four-gradient, i.e.,
$$A_{\mu}'=A_{\mu} +\partial_{\mu} \chi$$
must give the same equations of motion as ##A##, and this is the case for our "minimal ansatz" too, because under this "gauge transformation" the interaction Lagrangian changes to
$$L_{\text{int}}'=-\frac{q}{c} \dot{x}^{\mu} (A_{\mu} + \partial_{\mu} \chi) = -\frac{q}{c} \dot{x} \cdot A - \frac{q}{c} \mathrm{d}_\lambda \chi,$$
i.e., ##L'## differs from ##L## only by an additive total ##\lambda## deriviative which doesn't change the equations of motion. So the gauge transformation leads to an equivalent Lagrangian and thus the equation of states are gauge invariant as it must be.