Yes.
Note, however, that in general there are many $\tau$ that work. You found one; here's another: $\tau= (1,8,5,2,9,4,6,7,3).$ Indeed, $\tau\alpha\tau^{-1} = (\tau(1)\tau(2))(\tau(7)\tau(8))(\tau(3)\tau(4)\tau(5)) = (8,9)(3,5)(1,6,2)=\beta.$
Theorem. Two permutations $\alpha$ and $\beta$ are conjugate in $S_n$ if and only if they have the same cycle structure.
The proof provides an algorithm for finding a $\tau$ that works.
If $\alpha$ and $\beta$ are conjugate, then they have the same cycle structure. This, because the conjugate of an $n$-cycle is an $n$-cycle, and the conjugate of a product is a product of conjugates.
Conversely, suppose that $\alpha$ and $\beta$ have the same cycle structure. Say \alpha = \sigma_1\cdots\sigma_m,\quad \beta=\sigma'_1\cdots \sigma'_m where $\sigma_i$ and \sigma'_i are $n_i$-cycles. Write $\alpha$ and $\beta$ one above the other, so that cycles of the same length coincide; interpret this as a $2$-line description of a permutation, completing it to an element of $\sigma_n$ any way you want.
For example, with the two permutation you have above, $\alpha=(1,2)(7,8)(3,4,5)$, $\beta=(3,5)(8,9)(1,6,2)$, we have: $\left(\begin{array}{ccccccccc} 1 & 2 & 7 & 8 & 3 & 4 & 5 & & &\\ 3 & 5 & 8 & 9 & 1 & 6 & 2 & & & \end{array}\right)$ Note that the top line is missing $6$ and $9$, and the bottom line is missing $4$ and $7$; we can add them any way we want; for example, $\left(\begin{array}{cccccccc} 1 & 2 & 7 & 8 & 3 & 4 & 5 &6 & 9\\ 3 & 5 & 8 & 9 & 1 & 6 & 2 & 7 & 4 \end{array}\right)$ Now viewing this as a 2-line decription of a permutation, we get $\tau = (1,3)(2,5)(7,8,9,4,6)$ as one possibility. If you order the cycles differently (so long as they match), or reorder the terms within the cycle, you may get a different $\tau$. For instance, writing instead $\begin{align*} \alpha &= (12)(78)(453)\\ \beta &= (89)(53)(162) \end{align*}$ we get $\left(\begin{array}{ccccccccc} 1 & 2 & 7 & 8 & 4 & 5 & 3 & &\\ 8 & 9 & 5 & 3 & 1 & 6 & 2 & & \end{array}\right)$ with $6$ and $9$ in the top line going to $4$ and $7$ in some way; randomly choosing one, $\left(\begin{array}{ccccccccc} 1 & 2 & 7 & 8 & 4 & 5 & 3 & 6 & 9 \\ 8 & 9 & 5 & 3 & 1 & 6 & 2 & 4 & 7 \end{array}\right)$ we get $\tau = (1,8,3,2,9,7,5,6,4)$.
To find out if the permutations are conjugate in $A_n$, however, is a bit trickier: it is necessary that they have the same cycle structure, but in general it is not sufficient. For instance, in $S_3$ the permutations $(123)$ and $(132)$ are conjugate (for example, conjugate via $(23)$); but in $A_3$ they are not (since $A_3$ is abelian, different elements cannot be conjugate).