Use 2 relays. One needs to be strong enough to handle whatever current/voltage the starter motor requires.
Wire the starter relay's normally-open contacts to the key switch's starter contacts. Wire the relay coil, using a transistor to provide enough current, to an output pin on the PIC.
Wire the 2nd relay's normally-open contacts to the ignition-off contacts on the key switch. Wire the relay coil, using a transistor to provide enough current, to an output pin on the PIC.
Also wire the RPM sensor into an input pin on the PIC. Program the PIC to start the engine by engaging the starter and monitoring the RPM signal. When the engine catches, the RPM should increase and the PIC can disengage the starter, and continue to monitor the RPM to ensure the engine continues to run. Repeat the start attempt if necessary.
To stop the engine, engage the ignition-kill relay and wait for the RPM signal to stop, meaning the engine has stopped. Then disengage the ignition-kill relay.
Alternatively, you could put the ignition-kill on the normally closed contacts of a SPDT relay and then the ignition will be "off" by default (for safety). When the PIC wants the engine to run, it would engage the relay, disconnecting the ignition-off short circuit, and then start the engine. Then disengage the ignition relay to stop the engine.