As requested, here is a summary of the points raised in the comments.
The argument as posted in the question is very nearly complete.
As is true for any homomorphism, $Ker(\phi)$ is a normal subgroup. Of course, $S_5$ really hasn't got any normal subgroups. There is $S_5$ itself, the trivial group, and $A_5$. Now, as was sorted out in the question itself, the fact that all the $5$-Sylow subgroups are conjugate implies that $Im(\phi)$ is non-trivial, it has to have at least $6$ elements! It follows that $Ker(\phi)≤20$. That rules out both the complete group $S_5$ and the alternating group $A_5$, so $Ker(\phi)$ must be trivial. As was pointed out (correctly) in the question this is all that was needed to complete the argument.
I don't see how Rotman's construction can easily be used to find an outer automorphism of order $2$. That method uses the action on the cosets of a transitive subgroup of $S_6$ that is isomorphic to $S_5$. But the resulting outer automorphism depends on the numbering of the six cosets, and there are $720$ possible numberings. So you are effectively just looking for the innter automorphism $\gamma_\sigma$ that you describe.
I think the easiest way to do this is just to write down an outer automorphism of order $2$. To define the automorphism it suffices to specify the images of the transpositions $(1,2),(2,3),(3,4),(4,5),(5,6)$, each of which should be the product of three disjoint transpositions.
From the Coxeter presentation of $S_6$, it follows that such an assignment will define an automorphism provided that the images of two generators $x,y$ commute if and only if $x$ and $y$ do. This makes it possible to find the sought after automorphism of order 2 without too much difficulty.
I did this and found the automorphism of of order 2 below. This was not so hard. I knew that the iamges of $(1,2)$, $(3,4)$ and $(5,6)$ must all commute, so I wrote those down first, then I just found the images of $(2,3)$ and $(4,5)$ by trial and error.
$(1,2) \mapsto (1,2)(3,4)(5,6)$;
$(2,3) \mapsto (1,6)(2,3)(4,5)$;
$(3,4) \mapsto (1,2)(3,5)(4,6)$;
$(4,5) \mapsto (1,4)(2,3)(5,6)$;
$(5,6) \mapsto (1,2)(3,6)(4,5)$.
Best Answer
Here is a nice direct application: subgroups of small index in $S_n$. Assume that $n\geq 5$, and let $H\leq S_n$ be a subgroup of index at most $n$. Then either $H$ is $A_n, S_n$, or a stabilizer of some element $1\leq i \leq n$ in $S_n$, except if $n=6$. If $n=6$, then $S_6$ can be viewed as the group of all permutation of the 6 elements of the projective line over $\mathbb{F}_5$. But the group of projective transformations $PGL(2,5)$ form an index 6 subgroup.
The connection is: if $H\leq S_n$ with index $k$, then the action of $S_n$ on the left cosets of $H$ by left multiplication defines a homomorphism $\varphi: S_n\rightarrow S_k$. If $k< n$, then $\varphi$ cannot be injective. But as $n\geq 5$, the only possible kernels are $A_n, S_n$, yielding these subgroups of small indices. If $k=n$, then $\varphi$ can be injective. However, in that case it has to be surjective. So $\varphi\in Aut(S_n)$. Inner automorphims correspond to the stabilizers. Outer automorphisms correspond to different index $n$ subgroups. (Think about it.)
This line of thought can be extended to obtain simple proofs to results such as $PGL(2,5)\cong S_5$ and $PSL(2,5)\cong A_5$.