Soft errors in combinational logic circuits are emerging as a significant reliability concern for nano scale VLSI designs. This paper presents a novel sensitivity-based gate sizing methodology to reduce the soft error rate (SER) of combinational circuits in the presence of process variations. The proposed method is based on modeling the statistics of SER of the circuit gates as a random variable to formulate a statistical optimization problem. A backward traversing algorithm with capability for incremental analysis is developed for computing the distribution of circuit gates of SER random variables. We present a gate resizing algorithm in which the gates with the most contribution to the circuit SER are selected in a candidate set using a statistical ordering approach. The proposed algorithm trades off SER reduction and area overheads. The experimental results show that using the proposed methodology, the circuit statistical SER can be reduced by up to 56.4% compared with the 14.8% SER reduction of a circuit obtained using the worst case methodology at the expense of 10% area overhead under 10% process variation ratio. The results also show that the proposed method achieves about 40% more SER reduction compared with that obtained using closed-form analysis for statistical soft error rate estimation (CASSER), the most recently published similar work, in the same experimental conditions. Comparing the runtime of the proposed optimization algorithm with the optimization based on CASSER, it is observed that the proposed method is two orders of magnitude faster than CASSER due to its incremental analysis property.