The "sometimes cranks, sometimes starts" description sounds like there are two issues present at the same time.
My recommended strategy would be to address the intermittent cranking first. Intermittent starting could be something as simple as a bad battery as Anarach explains.
With intermittent cranking, the culprit could be a bad starter motor but since this has already been replaced (presumably with one that is new or in working condition) the issue is likely elsewhere.
Based on the symptoms described, there seems to be trouble with sending current to the starter motor. Here are two possible culprits:
It could well be that the solenoid inside relay is sticking, preventing the switch on the starter side from closing and turning the engine over. This would explain why sometimes you do not hear the starter relay click (complete silence).
Bad ignition switch.
If the ignition switch isn't completing the circuit to the starter relay, the car won't start. I'm a little skeptical that this is an issue given that the dashboard lights come on when the key is in the 'On' position but it is a distinct possibility.
I recommend testing the starter relay first before looking further upstream for potential issues.