Rather than discuss via comments, here's an explicit list of steps/hints. Perhaps you can look at them only when stuck:
Step 1. Admittedly, the integral you mentioned is not easy. Here's one approach:
\begin{align*}
\phi &= \int \frac{k \, d\theta}{\sin \theta \sqrt{ \sin^2 \theta-k^2}}
= \int\frac{k \, d \theta}{\sin^2\theta\sqrt{1-k^2\csc^2\theta}}
= \int\frac{k \csc^2 \theta \, d \theta}{\sqrt{1-k^2(1+\cot^2 \theta)}}.
\end{align*}
Now use a $u$-sub.
Step 2. Setting $u=\cot \theta$, we have $du=d(\cot \theta)=-\csc^2 \theta \, d\theta$, hence
\begin{align*}
\phi &= \int \frac{-k \, du}{\sqrt{1-k^2(1+u^2)}} = -\int \frac{ \, du}{\sqrt{\left(\frac{1-k^2}{k^2}\right) -u^2}}.
\end{align*}
Step 3. Using the formula $\int (a^2-x^2)^{-1/2} \, dx = \sin^{-1}(x/a)$, we have
\begin{align*}
\phi= - \sin^{-1}\left(\frac{u}{\sqrt{(1-k^2)/k^2}}\right)+C= -\sin^{-1}\left(\frac{k \cot \theta}{\sqrt{1-k^2}}\right)+C.
\end{align*}
Step 4. Compose with sine and use sum/difference formulas: $$k \cot \theta / \sqrt{1-k^2} = \sin(C-\phi)=\sin(C)\cos(\phi)-\cos(C)\sin(\phi).$$
Multiplying by $\sin \theta$, this gives
$$ k \cos \theta /\sqrt{1-k^2} = \sin (C) \cos (\phi) \sin (\theta)-\cos (C)\sin(\phi) \sin(\theta).$$
Step 5. Switch back to Cartesian coordinates:
$$\frac{k}{ \sqrt{1-k^2}}\cdot \frac{z}{a} = \sin(C) \cdot \frac{x}{a} - \cos(C) \cdot \frac{y}{a}.$$
Note that $k$ and $C$ are constants, so this is a linear relation of $x$, $y$, and $z$. What set of points satisfies such a relation? When you intersect the sphere with this set, you get a geodesic.