Theorem 1 in http://www.zbmath.org/?q=an:00912201 (J. Loss On the conjugacy problem for automorphisms of free groups. Topology 35, n.3 p779-806, 1996) states
"The conjugacy problem for the irreducible outer automorphisms of a free group admits a solution."