Let $\text{Odd}_n$ denote the set of odd permutations in $S_n$. Fix an element $\alpha \in \text{Odd}_n$, and define a function $f\colon A_n \to \text{Odd}_n$ by
$$
f(\sigma) \;=\; \alpha\sigma.
$$
I claim that $f$ is a bijection.
To prove that $f$ is one-to-one, suppose that $f(\sigma) = f(\sigma')$ for some $\sigma,\sigma' \in A_n$. Then $\alpha\sigma = \alpha\sigma'$, and therefore $\sigma=\sigma'$.
To prove that $f$ is onto, let $\beta \in \text{Odd}_n$. Then $\alpha^{-1}\beta$ is an even permutation and $f(\alpha^{-1}\beta) = \beta$, which proves that $f$ is onto.
We conclude that $|A_n| = |\text{Odd}_n|$, and therefore $|A_n| = |S_n|/2$.
When we're talking about the degree of a permutation group, the actual group structure doesn't matter. So in your example, the fact that $5 \equiv 2 \pmod 3$ is completely irrelevant; all that matters is that $C_3$ is (somehow) acting on $\{1, 2, 3, 4, 5\}$, and consequently will be said to have degree $5 = \left\lvert \{1, 2, 3, 4, 5\} \right\rvert$ in this case. In fact, if we're thinking about the action of any group on $\{1, 2, 3, 4, 5\}$, it will be said to have degree $5$, in that situation.
The term degree in this context is relative; it's not an intrinsic property of a group, but a property of the group action. It's similar to how a polynomial like $x^2 + 1$ would be considered irreducible -- over $\Bbb R$. But it can be factored as $(x - i)(x + i)$ over $\Bbb C$; the context is extremely relevant.
So, it's probably helpful to think of a permutation group as a whole bunch of data tied together: a group $G$, a set $\Omega$, and the action $G \times \Omega \to \Omega$ (or if you prefer, the homomorphism $\phi: G \to {\rm Sym}(\Omega)$) of $G$ on $\Omega$.
Example: The group of rotational symmetries of a cube is the symmetric group ${\rm Sym}(4)$, the full permutation group of the four diagonals of the cube. Thus we can think of ${\rm Sym}(4)$ as a permutation group in several ways, including but definitely not limited to:
A permutation group of degree $4$, if we think of it as acting on the diagonals of the cube.
A permutation group of degree $6$, if we think of it as acting on the faces of the cube.
A permutation group of degree $12$, if we think of it as acting on the edges of the cube, or
A permutation group of degree $8$, if we think of it as acting on the vertices of the cube.
Any subgroups of ${\rm Sym}(4)$, including $C_3$, also act on any of the above sets, and would have the same degrees in each situation.
Best Answer
The order of a permutation is the least common multiple of its cycle lengths. If the order is $4$, all cycle lengths must be $1$, $2$ or $4$, and at least one must be $4$. The cycle lengths must add up to $6$. That leaves the two options $4,2$ and $4,1,1$. The first is even and the second odd, so the only odd permutations of order $4$ in $S_6$ are the $4$-cycles. These can be counted by choosing the two fixed points in $\binom62$ ways and choosing one of $3!$ cyclically inequivalent orders in the $4$-cycle, for a total of $\binom62\cdot3!=90$.