For ease of formatting and explanation, I'll be doing everything for the $5 \times 5$ example. However, the same trick works for any $n \times n$ antisymmetric matrix (though slightly differently for even $n$).
Suppose
$$
A =
\begin{pmatrix}0&0&0&0&a_{15}\\0&0&0&a_{24}&0\\0&0&a_{33}&0&0\\0&a_{42}&0&0&0\\a_{51}&0&0&0&0 \end{pmatrix}
$$
Here's a neat trick: we note that
$$
A^2 = \pmatrix{
a_{15}a_{51}&&&&\\
&a_{24}a_{42}&&&\\
&&(a_{33})^2&&\\
&&&a_{24}a_{42}&\\
&&&&a_{15}a_{51}\\
}
$$
So, the eigenvalues of $A^2$ are precisely $\{a_{15}a_{51}, a_{24}a_{42}, (a_{33})^2\}$.
Now, note that if $\lambda$ is an eigenvalue of $A$, then $\lambda^2$ must be an eigenvalue of $A^2$. This gives you six candidates for the eigenvalues of $A$.
In fact, with more thorough analysis, we can guarantee that the eigenvalues will be precisely $\lambda = \pm \sqrt{a_{i,(n+1-i)}a_{(n+1-i),i}}$ for $i = 1,\dots,\lfloor n/2\rfloor$ and, for odd $n$, $\lambda = a_{(n+1)/2,(n+1)/2}$.
Proof that this is the case: Let $e_1,\dots,e_n$ denote the standard basis vectors. Let $S_{ij}$ denote the span of the vectors $e_i$ and $e_j$.
Note that $A$ is invariant over $S_{i(n-i)}$ for $i = 1,\dots,\lfloor n/2\rfloor$. We may then consider the restriction $A_{i(n-i)}: S_{i(n-i)} \to S_{i(n-i)}$, which can be represented by the matrix
$$
\pmatrix{0 & a_{i(n-i)}\\a_{(n-i)i} & 0}
$$
It suffices to find the eigenvalues of this transformation.
For the case of an odd $n$, it is sufficient to note that $a_{(n+1)/2,(n+1)/2}$ lies on the diagonal with zeros in its row and column.
Another explanation: denote the matrix
$S = \pmatrix{e_1 & e_{n} & e_2 & e_{n-1} & \cdots}$
Noting that $S$ is orthogonal (i.e. $S^{-1} = S^{T}$), we find that
$$
SAS^{-1} =
\pmatrix{
0&a_{1,n}\\
a_{n,1}&0\\
&&0&a_{2,n-1}\\
&&a_{n-1,2}&0\\
&&&&\ddots
}
$$
This matrix is similar, and therefore has the same eigenvalues. However, it is also block diagonal.
Best Answer
Your idea is good. If $n$ is even, you will need $\frac{n}{2}$ swap operations
$$ n \leftrightarrow 1, (n-1) \leftrightarrow 2, \ldots, \frac{n}{2}+1 \leftrightarrow \frac{n}{2}. $$
If $n$ is odd, you will need $\frac{n-1}{2}$ swap operations. Try to check that this works for small values of $n$.