In renewable penetrated power systems, frequency instability arises due to the volatile nature of renewable energy sources (RES) and load disturbances. The traditional load frequency control (LFC) strategy from conventional power sources (CPS) alone unable to control the frequency deviations caused by the aforementioned disturbances. Therefore, it is essential to modify the structure of LFC, to handle the disturbances caused by the RES and load. With regards to the above problem, this work proposes a novel coordinated LFC strategy with modified control signal to have Plug-in Hybrid Electric Vehicles (PHEVs) for frequency stability enhancement of the Japanese power system. Where, the coordinated control strategy is based on the PID controller, which is optimally tuned by the recently developed JAYA Algorithm (JA). Numerous simulations are performed with the proposed methodology and, the results have confirmed the effectiveness of a proposed approach over some recent and well-known techniques in literature. Furthermore, simulation results reveal that the proposed coordinated approach significantly minimizing the frequency deviations compared to the JAYA optimized LFC without PHEVs & with PHEVs but no coordination.