You can send the command and signature split over multiple messages. It is already common to tunnel other data over CAN with this method.
The signing key would of course be unique per ECU/keyfob that needs to sign stuff so dumping another ECU doesn't help you crack it.
Loading a new private key from the server? Well, thief's device can probably pretend to be a server and load a new private key into the control unit behaving as a master of immobilizer. Then the thief will get car and instantly new set of keys.
Erm... using the LSB of a network RX timer is common way to add entropy (and perfectly feasible here). You could also use the LSB of the +voltage rail sense or the thermometer that probably exists on your MCU.