This paper develops a new approach for solving optimal time and energy trajectory planning problems for Autonomous Underwater Vehicles (AUVs) in transient, 3D, ocean currents. Realistic forecasts using an Ocean General Circulation Model (OGCM) are used for this purpose. The approach is based on decomposing the problem into a minimal time problem, followed by minimal energy subproblems. In both cases, a non-linear programming (NLP) formulation is adopted. The scheme is demonstrated for time-energy trajectory planning problems in the Gulf of Aden. In particular, the numerical experiments illustrate the capability of generating Pareto optimal solutions in a broad range of mission durations. In addition, the analysis also highlights how the methodology effectively exploits both the vertical structure of the current field, as well as its unsteadiness, namely to minimize travel time and energy consumption.