Circuit performance has been the key design constraint for over a decade. Variable-latency design (VLD) paradigm was proposed for optimizing the overall performance in terms of throughput. In addition, process variations and aging effects manifest themselves as gate delay shifts, and in turn cause variability of circuit timing (timing variability). Required for dealing with the impact of timing variability better, detailed evaluation and analysis of circuit timing for VLD are actually not straightforward. In this paper, we present a systematic methodology for analyzing a VLD circuit, and identifying critical 1-cycle and 2-cycle paths/gates. Based on the criticality analysis, a gate sizing framework using particle swarm optimization (PSO) is proposed. Our objective is, in a less pessimistic fashion, making constructed VLD circuits better (less vulnerable to timing variability). The proposed framework is experimentally verified to be runtime-efficient and able to provide promising results. On average, an extra timing margin of 11% can be obtained without lengthening the clock period, and only 4% area overhead is introduced.