For load cells I have good luck with simple instrumentation amps like TI's INA122's powered off the 5 V line from Arduino, the output on it is 0 - 5V. In your case I would check if you can operate your amp with a lower voltage so your output does not exceed 5 V. Alternatively, you could probably use a simple voltage divider with two resistors.