Should kernel size always be a prime number?
Odd numbers, usually, but not necessarily. This can depend on the problem at hand. The odd length of the side of the kernel is used in order to emphasize the center of the kernel. For a more detailed discussion of the geometry of kernels and convnets have a look at this thesis.