These conditions are not equivalent, only under several assumptions. A good reference are chapters 1 and 3 of Henneaux' and Teitelboim's "Quantization of gauge systems".
The "proper" definition of a gauge theory that relies neither on a Hamiltonian nor on a Lagrangian formalism explicitly is that the solutions $q(t)$ to the equations of motion contain some arbitrary functions of time, i.e. are not uniquely determined by the initial conditions. This is the root cause of the notion that "gauge degrees of freedom are redundant".
In the Lagrangian formalism, the equations of motion are the Euler-Lagrange equations:
$$ \frac{\mathrm{d}}{\mathrm{d}t}\frac{\partial L}{\partial \dot{q}^i} - \frac{\partial L}{\partial q^i} = \ddot{q}^j \frac{\partial L}{\partial \dot{q}^j \partial \dot{q}^i} + \dot{q}^j \frac{\partial L}{\partial q^j\partial \dot{q}^i} - \frac{\partial L}{\partial q^i} = 0 \tag{1}$$
which yields
$$ \frac{\partial L}{\partial \dot{q}^j \partial \dot{q}^i} \ddot{q}^j = - \dot{q}^j \frac{\partial L}{\partial q^j\partial \dot{q}^i} + \frac{\partial L}{\partial q^i}\tag{2},$$
showing that the accelerations $\ddot{q}^j$ are determined by the velocities and positions if and only if the matrix $\frac{\partial L}{\partial \dot{q}^j \partial \dot{q}^i} $ is non-degenerate. This is why the condition
$$ \det\left(\frac{\partial L}{\partial \dot{q}^j \partial \dot{q}^i} \right) = 0\tag{3}$$
is the relevant condition for a Lagrangian gauge theory. Note that we have thus far not used the notion of a "gauge transformation" at all.
When passing to the Hamiltonian formalism with momenta $p_i$, eq. (3) manifests as a number of off-shell relations $\phi_k(q,p) = 0$ among the momenta, called the primary constraints. To these we have to add the on-shell secondary constraints obtained by imposing $\dot{\phi}_k = 0$. We also denote these by $\phi_k$ (and they potentially in turn generate tertiary constraints, and so on), since we will eventually be interested in the on-shell case, anyway. All these constraints fall into two more relevant classes, creatively called first-class and second-class:
A first-class constraint is one that Poisson-commutes with all other constraints, i.e. $\{\phi_i,\phi_j\} = 0$ for all $j$. We'll denote these as $\gamma_i$. A second-class constraint is one that doesn't, we'll denote these as $\chi_i$.
The first-class constraints generate gauge transformations: The total Hamiltonian whose equations of motion are equivalent to those of the degenerate Lagrangian system can be written as
$$ H = H_0 + v^i \gamma_i,$$
where $H_0$ is a first-class function and the $v^i$ are arbitrary functions of time, corresponding to the arbitrary functions from our definition in the beginning. Looking at a phase space observable $f$ at a time $t + \delta t$ and considering two different choices $v^i, v^i + \delta v^i$ at time $t$, we find that
$$ \delta f = \delta v^i\delta t \{f,\gamma_i\},\tag{4}$$
but this choice should make no difference since the $v^i$ were arbitrary to begin with! Therefore eq. (4) is the manifestation of a gauge transformation in the Hamiltonian formalism, and the first-class constraints generate such gauge transformations. Note: A more careful argumentation of the above concludes only that all primary first-class constraints generate gauge transformations, and the statement that all first-class constraints generate gauge transformations is called the Dirac conjecture, which is usually assumed to be true, but to which counterexamples exist, see Henneaux/Teitelboim.
Second-class constraints do not generate gauge transformations: This is evident because eq. (4) tells us that $\delta \chi_i \neq 0$ for at least one $\chi_j$, meaning they would transform the constraints themselves, mapping allowed states of the system to disallowed states. This is consistent with noting that upon fixing a gauge - selecting an ad hoc additional set of constraints $C_i(q,p) = 0$ such that no arbitrary functions are left in the solutions to the equations of motion - all constraints become second-class.
Finally, we can come to the discussion of actual gauge symmetries of the action that we know and love. An infinitesimal arbitrary gauge symmetry of an action $S = \int L(q,\dot{q},t)\mathrm{d}t$ has the form
$$ \delta q^i = f^{(0)} \epsilon + f^{(1)} \dot{\epsilon} + \dots = \sum_{i=1}^{l} f^{(i)} \frac{\mathrm{d}^i \epsilon}{\mathrm{d}t^i},$$
where the $f^{(i)}$ are functions of the $q$ and their derivatives and $\epsilon$ is an arbitrary function of time. The Hamiltonian action is
$$ S_H = \int (p_i \dot{q}^i - H_0 - v^i \gamma_i)\mathrm{d}t,$$
and yields the original Lagrangian action upon elimination of the Lagrange multipliers $v^i$, preserving all symmetries, meaning a gauge symmetry of $S_H$ is also one of $S_L$.
It is rather tedious, but possible, to explicitly verify that every gauge transformation generated by eq. (4) is a gauge symmetry of this action, see again Henneaux/Teitelboim, chapter 3. However, we need the Dirac conjecture to know that all constraints generate gauge transformations, and that there are no extra gauge symmetries.
The following list of assumptions (once again from H/T) is sufficent but not necessary to establish the Dirac conjecture:
The process which finds the secondary, tertiary, etc. constraints never yields the same constraint at two different steps, meaning it is well-defined to ask of a constraint whether it is primary or tertiary.
The process which finds the higher constraints cleanly separates first- and second-class constraints, i.e. a first-class constraint never generates a second-class constraint and vice versa.
The first-class brackets $[H,\gamma_a] = V_a^b \gamma_b$ are "sufficiently nice functions", in particular the matrices $V_{m_i}^{m_j}$ where $m_i$ denotes the indices for constraints of a particular generation, have maximal rank.
Altogether, we find that if the above conditions are fulfilled (or if the Dirac conjecture holds anyway) and if the degeneracy eq. (3) is not solely caused by second-class constraints, then there is an equivalence between the degeneracy and the existence of gauge symmetries of the action. Note that, by our initial definition of a gauge theory, this means that not all "gauge theories" possess gauge transformations!
