Starter problem

It could also be a bad signal from the key switch.Or a bad ground at the NSS.
The next time it happens just bridge the two largest studs on the relay withe a large screwdriver or something similar. If the clicking is gone, and it cranks normally, then it will likely be one of the above.
The key switch is off for this test.