You would need a bridge amplifier or AFE (Analog Front End). The easiest way is to buy some shield for arduino. Or you could buy an Arduino clone from Analog devices with additional bridge amplifier. AD sells many industrial grade quality boards with examples with their Arduino clone.
This could be a good candidate Arduino AFE for your requirements:https://wiki.analog.com/resources/eval/user-guides/eval-adicup360/hardware/cn0216
Your sensor bridge specification are valid for 12V supply, but I don't thing it would matter if you put a lower voltage supply. The only thing is that the output will now be lower, so you would need to calibrate your device.
Your gauge sensor outputs typically 25mV at 12Vdc supply, therefore we could say it has a sensitivity of 25mV/12V = 2.083mV/V.
The Tedeah Huntleigh Model 1042 load cell used for test on the EVAL-CN0216-ARDZ Shield has a sensitivity of 2mV/V. Therefore the suggested load cell AFE + ADC is a perfect match for your need.
The board is specified to work for a cell that has +/-10mV full-span output voltage. By default it is configured to bipolar signal, but you can change it to unipolar by software settings, if you want. The resolution is 15bit for +/-10mV peak to peak, that will bring to 14 bits if you leave it as default with a signal that changes in one direction only (unipolar). The input voltage is amplified with G=375. The maximum applied voltage is however 5v, so the real input range is 5/375= +/-13mV, which can give you enough margin for the zero offset unbalance.
Your sensor will give as spec. the maximum 25mV at 12v. S_max= 25mV/12V = 2.083mV which can give the maximum output voltage 5*2.083 = +/-10.415mV. Or the minimal full span S_min = 15mV/12V = 1.25mV/V; 5*1.25mV/V = +/-6.25mV. Amplifying the signal with instrumentation amplifier gives: 375*10.41mV = +/-3.905V for max sensitivity or 375*6.25mV= +/-2.343V for minimal sensitivity of the sensor. Both regions are well in the measuring range, you could expect a little less resolution using less sensitive sensor, but we could say that resolution is true 13 bits over the pressure range, at sampling rate 9.5Hz.
One important thing: you would need to power the Arduino board with external PSU at least 7VDC, because the reference voltage 5VDC is derived from Vin pin with the use of LDO. So, you can't use this board and power the Arduino from USB.