You have what is known as a "multi-wire branch circuit", where two otherwise independent circuits share the same neutral return back to the electrical panel. Wiring the GFCIs in a naive manner won't help you here, because in a shared neutral situation, the GFCIs won't see the return currents coming back from the "other" hot wire, and will trip as they are designed to do as a result. However, there are two options to rectify this, depending on your situation:
1. Replace the breakers with a two-pole GFCI circuit breaker
Depending on the make and model of your electrical panel, you may be able to obtain a two-pole GFCI circuit breaker for it; in that case, and if your kitchen circuits come from adjacent breaker slots in the panel, you can replace the kitchen circuit breakers with a single two-pole GFCI breaker and get GFCI protection without rewiring the outlets.
2. Install GFCI receptacles so that each receptacle device is on a different leg.
Right now, you have what's called a "mixed leg" shared neutral circuit, where both legs are present at each receptacle device, instead of having half the receptacle devices attached to one leg and half to the other. However, you'd have to pull a 12/2/2 instead of your current 12/3 for all devices attached downstream of the first GFCI, or retrofit all outlets on this circuit to be GFCI outlets, which is undesirable.
Borrowing a diagram from this answer by Tester101: