As we know, for any vector $v$ that we want to rotate, the rotated vector $v_{rot}$ about some axis $u$ is equivalent to the sum of the parallel component of $v$ and $u$ plus the planarly-rotated perpendicular component of $v$, ala Rodriguez formula: https://people.eecs.berkeley.edu/~ug/slide/pipeline/assignments/as5/rotation.html
$v_{rot} = v_{||} + v_{\perp rot}$
Given two initial specified vectors $v$ and $v_{rot}$, we can always generate some axis $u$ by taking the cross product $\text{cross} (v, v_{rot})$ where $v$ is the initial vector.
Let's call this $u_{cross}$. $u_{cross}$ is always associated with a specific angle, $\theta_{cross}$, which can be calculated using this: https://stackoverflow.com/questions/5188561/signed-angle-between-two-3d-vectors-with-same-origin-within-the-same-plane
How do we prove that $\theta_{cross}$ is the smallest rotation angle across all $u$?
The shortest possible rotation angle will have no component or rotation in the direction of either vector, because any rotation about $v$ or $v_{rot}$ results in the same vector $v$ or $v_{rot}$. Therefore, if given a rotation with some component in the direction of $v$ or $v_{rot}$, then there will be a shorter one, without this component.
Between $v$ and $v_{rot}$, the only vector that has this property is the one orthogonal to both $v$ and $v_{rot}$, and is given by the cross product. (I guess its opposite is also orthogonal, so you could use that one too, but the rotation angle about this vector has the same magnitude even if it is negative).
There is the interesting case is when $v = \pm v_{rot}$, where there are an infinite number of "shortest axes of rotation" all in the plane orthogonal to $v$ since there are an infinite number of orthogonal vectors.