Can you be more specific about the problem that you have? I assume you are using twinaxial cable and the current is low (i.e. transmitting signal, not power).
Capacitance is a function of the dielectric constant of the insulating (dielectric) material, plate area and distance between plates (C=k*A/d). In general, the easiest way is to change the "distance between plates". In other words, increase the thickness of insulation material (increase "d" and hence reduce "C"). You can also use small wire gauge (wires with larger AWG# or SWG#). By doing so, the "A" in the formula can be reduced a little bit so that "C" can be reduced too.
1. Bring down the voltage of sheaths of both the cables forcibly to zero, by connecting them to the common ground terminal. So, if the voltage difference itself is zero, it won't be necessary to bother about the capacitance. (*)
2. Use a twisted pair if it can be used in your system
* - Note that, if you have high voltage through one of the cables, bringing down the sheath voltage forcibly to zero would increase the electric field in the region between sheath and cable. So, to prevent dielectric discharge you should have an insulator with high dielectric strength between them.
Using a bridge sensing circuit, I believe the main problem with CM parasitic capacitances is that they can be slightly different, thus converting common-mode signals to differential signals.
One solution can be to introduce in the circuit accurate real capacitors (maybe trimmable), with a capacitance larger than the parasitics and connected in parallel with the parasitics and in the symmetrical position, so that value of the parasitics can be negligible in comparison (this is applicable only if the added capacitance does not impair the measurement). In alternative, a dummy cable, of the same type and of the same length of the one connected to the sensing element can be used in a symmetrical position of the bridge. Using shielded cables, the cable connected to the sensing element and the dummy cable could be shielded by the same shield.
These are just some suggestions which do not involve specific hardware or signal processing. Anyway, more complex solutions can be devised depending on the target accuracy.