Why does directional stability decrease at supersonic speeds?
It is a combination of several effects:


Aeroelasticity: With the higher forces at high speed, the structure deforms such that the effective flow angle at the tail surface is reduced.
The supersonic lift curve slope of the tail surface decreases with Mach while that of the fuselage stays roughly constant, so with higher Mach the tail contribution to stability shrinks while the destabilizing contribution of the fuselage stays the same.
Tail location: At supersonic speed the density of air on the upper fuselage is reduced while that on the bottom is increased. Since the vertical sits on top of the fuselage, it flies in rarefied air. Ventral fins, on the other hand, become more effective.


The supersonic lift curve slope is approximately $$c_{L\alpha}=\frac{4}{\sqrt{Ma^2-1}}\cdot\left(1-\frac{\lambda}{2\cdot AR\cdot\sqrt{Ma^2-1}}\right)$$
Note that the second term is for the influence of the triangular surface on the tip where the pressure difference is reduced. Nevertheless, it shows that lift curve slope of the vertical decreases with increasing Mach number.

For the fuselage, the lift curve slope is that of a slender body:$$c_{L\alpha}=\pi\cdot\frac{AR}{2}$$
Note that this equation is independent of Mach, so the destabilizing fuselage contribution stays constant over Mach.

For the beneficial influence of ventral fins see the diagram below which has been published by Lockheed in The F-104 Strafighter Test Pilot's Notebook by Glenn L. Reaves (source):