Why do we have redundant degrees of freedom? Preliminaries: Consider the homogenous Maxwell's equations 
$$\partial_\mu F^{\mu\nu}=0.$$
and
$$\partial_{\sigma} F_{\mu \nu}+\partial_{\mu} F_{\nu \sigma}+\partial_{\nu} F_{\sigma \mu}=0$$
Since $F^{\mu\nu}$ is antisymmetric there are a total of $\frac{16-4}{2} =6$ DOFs, all of which are physical. 

Now, let us introduce a gauge potential $A_\mu$ so that 
$$ F_{\mu\nu} = \partial_\mu A_\nu - \partial_\nu A_\mu $$
which also has 6 DOFs, and also leave the Maxwell equations invariant under a suitable transformation of $A_\mu$. However, we regard some of them as non-physical.

Question: Is my counting of degrees of freedom correct? If not, then where do these "extra" number of degrees arise in introducing the gauge potential $A_\mu$? If my counting is correct, then why are there redundant DOFs in $\partial_{[\mu}A_{\nu]}$ but not $F_{\mu\nu}$? 
 A: There aren't six degrees of freedom in the electromagnetic field, no matter how you write it. There are just six properties of the field that are easy to measure ($E_x$, $E_y$, $E_z$, $B_x$, $B_y$, and $B_z$). Similarly, a wave on a horizontal string has one degree of freedom, its height, even though one can measure its kinetic energy density, potential energy density, vertical velocity, and more. 
The general way of counting degrees of freedom is to go to a Lagrangian formulation and look at the dimension of its configuration space, minus constraints and gauge freedom. But a trick that works for free fields is to just see how many numbers are needed to describe each mode of the field; this works even if you're not using the actual degrees of freedom (the $A_\mu$).
For example, the modes of the electromagnetic field are plane waves. You can use Maxwell's equations to show that $E = c B$ and $\mathbf{E} \times \mathbf{B} \propto \mathbf{k}$. So for each wavenumber $\mathbf{k}$ there are only two things you fix to determine what the plane wave is, e.g. the magnitude of the electric field and the polarization. 
