<PAGE>
 
                                                                  Exhibit 10.5.4


                        EXECUTIVE EMPLOYMENT AGREEMENT
                        ------------------------------

  This Agreement made and entered into as of January 1, 1998 (the "Effective
Date") by and between PACIFIC GATEWAY EXCHANGE (the "Company") and ROBERT F.
CRAVER (the "Executive"),

                               WITNESSETH THAT:
                               --------------- 

     WHEREAS, the parties desire to enter into this Agreement pertaining to the
continued employment of the Executive by the Company;

     NOW THEREFORE, in consideration of the mutual covenants and agreements set
forth below, it is hereby covenanted and agreed by the Company and the Executive
as follows:

     1.  Employment Period.  Subject to the terms and conditions of this
         -----------------                                              
Agreement, the Company hereby agrees to employ the Executive during the
Employment Period (as defined below) and the Executive hereby agrees to remain
in the employ of the Company and to provide services during the Employment
Period in accordance with this Agreement.  The "Employment Period" shall be the
period beginning on the Effective Date and ending on the second anniversary
thereof.  After the second anniversary of the Effective Date, the Employment
Period shall be automatically extended for 12-month periods, unless one party to
this Agreement provides written notice of non-renewal to the other at least 90
days before the last day of the Employment Period.

     2.  Duties.  Subject to the terms of this Agreement, the Company hereby
         ------                                                             
agrees to employ the Executive as its Senior Vice President, International
Relations during the Employment Period, and the Executive hereby agrees to
remain in the employ of the Company during the Employment Period.  During the
Employment Period, while the Executive is employed by the Company, the Executive
shall devote substantially all of his business time, energies and talents to
serving as its Senior Vice President, International Relations.  The Executive
agrees that he shall perform his duties faithfully and efficiently subject to
the directions of the President of the Company (the "President").  The Executive
will have such authority and power as are inherent to the undertakings
applicable to his positions and necessary to carry out his responsibilities and
the duties required of him hereunder.

     3.  Compensation.  Subject to the terms and conditions of this Agreement,
         ------------                                                         
during the Employment Period while the Executive is employed by the Company, the
Company shall compensate him for his services as follows:
<PAGE>
 
     (a)  The Executive shall receive, for each 12-consecutive month period
          beginning on the Effective Date and each anniversary thereof, an
          annual salary of $150,000 (the "Salary"), which Salary shall be
          payable in substantially equal monthly installments.  The Executive's
          Salary rate shall be reviewed annually on or about the anniversary of
          the Effective Date, to determine whether an increase in the amount of
          Salary is appropriate.  In no event shall the Salary of the Executive
          be reduced to an amount that is less than the amount specified in this
          paragraph (a), or to an amount that is less than the amount that he
          was previously receiving.

     (b)  The Executive shall be entitled to incentive compensation in the form
          of an annual cash bonus that shall be determined by the President
          taking into consideration whether the Executive has met the
          performance targets set by the President for such year, (which shall
          be set by the President, in consultation with the Executive, on or
          about January 31 of each year), the relative contribution by the
          Executive to the business of the Company, the Company's financial
          performance for the year, general economic conditions, and such other
          factors as the President deems relevant.

     (c)  Except as otherwise specifically provided to the contrary in this
          Agreement, the Executive shall be provided with the retirement,
          welfare benefits and other fringe benefits to the same extent and on
          the same terms as those benefits are provided by the Company from time
          to time to the Company's other senior management employees.

     (d)  The Executive shall be reimbursed by the Company, on terms and
          conditions that are substantially similar to those that apply to other
          similarly situated senior management employees of the Company, for
          reasonable expenses for entertainment, travel, meals, lodging and
          similar items which are authorized by the Company and actually
          incurred by the Executive in the promotion of the Company's business.

     4.  Rights and Payments Upon Termination or Change in Control.  The
         ---------------------------------------------------------      
Executive's right to benefits and payments, if any, for periods after the date
on which his employment with the Company terminates for any reason (his
"Termination Date") shall be determined in accordance with this Section 4:

     (a)  Minimum Payments.  If the Executive's Termination Date occurs during
          ----------------                                                    
          the Employment Period for any reason, the Executive shall be entitled
          to the following payments, in addition to any payments or benefits to
          which the Executive may be entitled under the following provisions of
          this Section 4 (other than this paragraph (a)):

          (i)     his earned but unpaid Salary for the period ending on his
                  Termination Date; and

                                      -2-
<PAGE>
 
          (ii)    his accrued but unpaid vacation pay for the period ending with
                  his Termination Date, as determined in accordance with the
                  Company's policy as in effect from time to time.

          Payments to be made to the Executive pursuant to this paragraph 4(a)
          shall be made in a lump sum as soon as practicable after the
          Executive's Termination Date.  Except as may be otherwise expressly
          provided to the contrary in this Agreement, nothing in this Agreement
          shall be construed as requiring the Executive to be treated as
          employed by the Company following his Termination Date for purposes of
          any employee benefit plan or arrangement in which he may participate
          at such time.

     (b)  Termination By Company for Cause.  If the Executive's Termination Date
          --------------------------------                                      
          occurs during the Employment Period and is a result of the Company's
          termination of the Executive's employment on account of Cause (as
          defined in paragraph (g) below), then, except as agreed in writing
          between the Executive and the Company, the Executive shall have no
          right to future payments or benefits under this Agreement (and the
          Company shall have no obligation to make any such future payments or
          provide any such future benefits) for periods after the Executive's
          Termination Date.

     (c)  Termination for Death or Disability.  If the Executive's Termination
          -----------------------------------                                 
          Date occurs during the Employment Period on account of the Executive's
          death or disability (as defined below), then the Executive (or in the
          event of his death, his estate) shall be entitled to continuing
          payments of his Salary for the period commencing on his Termination
          Date and ending on the earliest of (i) 30 days from his Termination
          Date, (ii) the last day of the Employment Period, or (iii) in the case
          of the Executive's disability, the date on which the Executive
          violates the provisions of Section 6 of this Agreement.

     (d)  Termination for Good Reason or by the Company for Reasons Other Than
          --------------------------------------------------------------------
          Cause.  If the Executive's Termination Date occurs during the
          -----                                                        
          Employment Period and before the date of a Change in Control (as
          defined in Exhibit A hereto), and is a result of the Executive's
          termination of employment by the Company for any reason other than
          Cause or on account of termination by the Executive for Good Reason
          (as defined in paragraph (g)), and is not on account of the
          Executive's death, disability, or voluntary resignation, the mutual
          agreement of the parties or any other reason, then:

          (A)  The Executive shall receive from the Company for the period
          commencing on his Termination Date and ending on the earliest of (i)
          the 6-month anniversary of his Termination Date, (ii) the date on
          which the Executive violates the 

                                      -3-
<PAGE>
 
          provisions of Section 6 of this Agreement, or (iii) the date of the
          Executive's death, the Salary in effect as of his Termination Date
          (without regard to any reduction in such Salary which gives the
          Executive the right to termination employment for Good Reason),
          payable in accordance with the provisions of paragraph 3(a).

          (B)  Stock options awarded to the Executive under any option plans of
          the Company shall be 100% vested upon the occurrence of the
          Executive's Termination Date as described in this paragraph (d) and
          shall be exercisable for the period after the Termination Date as
          specified for vested options in the applicable option agreement.

     (e)  Termination for Voluntary Resignation, Mutual Agreement or Other
          ----------------------------------------------------------------
          Reasons.  If the Executive's Termination Date occurs during the
          -------                                                        
          Employment Period on account of his voluntary resignation, mutual
          agreement of the parties, or any reason other than those specified in
          paragraphs (b), (c) or (d) above then, except as agreed in writing
          between the Executive and the Company, the Executive shall have no
          right to future payments or benefits under this Agreement (and the
          Company shall have no obligation to make any such future payments or
          provide any such future benefits) for periods after the Executive's
          Termination Date.

     (f)  Termination Following a Change in Control.  If the Executive's
          -----------------------------------------                     
          Termination Date occurs within two years following a Change in
          Control, including a Termination Date occurring on the date of a
          Change in Control, on account of termination by the Company for
          reasons other than Cause or on account of termination by the Executive
          for Good Reason, then the Executive shall receive from the Company a
          lump sum payment equal to 6 months Salary in effect as of his
          Termination Date (without regard to any reduction in such Salary which
          gives the Executive the right to termination employment for Good
          Reason).

     (g)  Definitions.  For purposes of this Agreement:
          -----------                                  

          (i)  the term "Cause" shall mean (1) the willful and continued failure
               by the Executive to substantially perform his duties under this
               Agreement, other than by reason of his being disabled (as defined
               below), (2) the willful engaging by the Executive in conduct
               which is demonstrably and materially injurious to the Company or
               its affiliates, (3) conduct by the Executive that involves theft
               or fraud or, in connection with his duties under this Agreement,
               dishonesty, (4) Executive's violation of the provisions of
               Sections 6 or 7 hereof, or (5) conviction of felony involving
               moral turpitude;

                                      -4-
<PAGE>
 
         (ii)  no act, or failure to act, on the Executive's part shall be
               deemed "willful" unless done, or omitted to be done, by the
               Executive not in good faith and without reasonable belief that
               the Executive's action or omission was in the best interest of
               the Company; and

         (iii) the term "disability" shall mean the inability of the
               Executive, after reasonable accommodation, to continue to perform
               his duties under this Agreement on a full-time basis as a result
               of mental or physical illness, sickness or injury for a period of
               180 days within any 12-month period, as determined in the sole
               discretion of the Board of Directors of the Company; and

         (iii) the term "Good Reason" shall mean any of the following which
               occur without the Executive's consent and which are not corrected
               by the Company within 10 days of written notice to the Company by
               the Executive: (1) a diminution of the Executive's duties or the
               assignment to him of duties that are inconsistent in any
               substantial respect with the position, authority or
               responsibilities associated with the position of Senior Vice
               President, International Relations (2) a reduction in the
               Executive's Salary rate or bonus potential; or (3) a relocation,
               without the Executive's consent, of the Executive's principal
               office from his current office as of the Effective Date to an
               office that is more than 10 miles of the Executive's current
               office, except for required travel on Company business to an
               extent substantially consistent with the Executive's business
               travel obligations on the Effective Date.

Notwithstanding any other provision of this Agreement, the Executive shall
automatically cease to be an officer and/or director of the Company and its
affiliates as of his Termination Date.

     5.  Set-Off.  The Company shall be entitled to set off against the amounts
         -------                                                               
payable to the Executive under this Agreement, any amounts owed to the Company
or its affiliates by the Executive.

     6.  Confidential Information.  The Executive agrees that:
         ------------------------                             

     (a)  Except as may be required by the lawful order of a court or agency of
          competent jurisdiction or as necessary to carry out his duties to the
          Company and its affiliates, or except to the extent that the Executive
          has express authorization from the Company, he shall keep secret and
          confidential indefinitely all non-public information (including,
          without limitation, information regarding litigation and pending
          litigation) concerning the Company and its affiliates which was
          acquired by or disclosed to the Executive during the course of his
          employment with the Company or during the course of his consultation
          with the 

                                      -5-
<PAGE>
 
          Company following his termination of employment and not to disclose
          the same, either directly or indirectly, to any other person, firm, or
          business entity, or to use it in any way.

     (b)  Upon his Termination Date or at the Company's earlier request, he will
          promptly return to the Company any and all records, documents,
          physical property, information, computer disks or other materials
          relating to the business of the Company and its affiliates obtained by
          him during his course of employment with the Company.

     (c)  Nothing in the foregoing provisions of this Section 6 shall be
          construed so as to prevent the Executive from using, in connection
          with his employment for himself or an employer other than the Company
          or any of its affiliates, knowledge which was acquired by him during
          the course of his employment with the Company and its affiliates, and
          which is generally known to persons of his experience in other
          companies in the same industry.

     7.  Noncompetition.  During the Noncompetition Period (as defined below),
         --------------                                                       
the Executive agrees that he will not directly or indirectly engage in, assist,
perform services for, establish or open, or have any equity interest (other than
ownership of 5% or less of the outstanding stock of any corporation listed on
the New York or American Stock Exchange or included in the National Association
of Securities Dealers Automated Quotation System) in any person, firm,
corporation, or business entity (whether as an employee, officer, director,
agent, security holder, creditor, consultant, or otherwise) that engages in the
business of providing international or domestic long distance telephone
services.  Nothing in this Section 7 shall be construed as limiting the
Executive's duty of loyalty to the Company while he is employed by the Company,
or any other duty he may otherwise have to the Company while he is employed by
the Company.  For purposes of this Agreement, the "Noncompetition Period" shall
be the period while the Executive is employed by the Company and for the period,
if any, after the Executive's Termination Date that he is receiving payments
pursuant to Section 4 hereof.

     8.  Equitable Remedies.  The Executive acknowledges that the Company would
         ------------------                                                    
be irreparably injured by a violation of Sections 6 or 7 and agrees that the
Company, in addition to other remedies available to it for such breach or
threatened breach, shall be entitled to a preliminary injunction, temporary
restraining order, other equivalent relief, restraining the Executive from any
actual or threatened breach of Sections 6 or 7 without any bond or other
security being required.

     9.  Defense of Claims.  The Executive agrees that, on and after the
         -----------------                                              
Effective Date, he will cooperate with the Company and its affiliates in the
defense of any claims that may be made against the Company or its affiliates to
the extent that such claims may relate to services performed by him for the
Company.  To the extent travel is required to comply with the 

                                      -6-
<PAGE>
 
requirements of this Section 9, the Company shall, to the extent possible,
provide the Executive with notice at least 10 days prior to the date on which
such travel would be required and the Company agrees to reimburse the Executive
for all of his reasonable actual expenses associated with such travel; provided,
however, that if the Company reasonably expects the travel to be extensive or
unduly burdensome to the Executive from a financial perspective, the Company may
provide to the Executive pre-paid tickets for transportation in connection with
such travel.

     10.  Notices.  Notices provided for in this Agreement shall be in writing
          -------                                                             
and shall be deemed to have been duly received when delivered in person or sent
by facsimile transmission, on the first business day after it is sent by air
express courier service or on the second business day following deposit in the
United States registered or certified mail, return receipt requested, postage
prepaid and addressed, in the case of the Company to the following address:

          Pacific Gateway Exchange
          533 Airport Boulevard, Suite 505
          Burlingame, California 94010

          Attention: Howard A. Neckowitz

or to the Executive at his last residence address as shown on the Company's
payroll records, or such other address as either party may have furnished to the
other in writing in accordance herewith, except that a notice of change of
address shall be effective only upon actual receipt.

     11.  Withholding.  All compensation payable under this Agreement shall be
          -----------                                                         
subject to customary withholding taxes and other employment taxes as required
with respect to compensation paid by a corporation to an employee and the amount
of compensation payable hereunder shall be reduced appropriately to reflect the
amount of any required withholding.  The Company shall have no obligation to
make any payments to the Executive or to make the Executive whole for the amount
of any required taxes.
 
     12.  Successors.  This Agreement shall be binding on, and inure to the
          ----------                                                       
benefit of, the Company and its successors and assigns and any person acquiring,
whether by merger, reorganization, consolidation, by purchase of assets or
otherwise, all or substantially all of the assets of the Company.

     13.  Nonalienation.  The interests of the Executive under this Agreement
          -------------                                                      
are not subject to the claims of his creditors, other than the Company, and may
not otherwise be voluntarily or involuntarily assigned, alienated or encumbered.

     14.  Waiver of Breach.  The waiver by either the Company or the Executive
          ----------------                                                    
of a breach of any provision of this Agreement shall not operate as or be deemed
a waiver of any subsequent breach by either the Company or the Executive.
Continuation of payments hereunder by the 

                                      -7-
<PAGE>
 
Company following a breach by the Executive of any provision of this Agreement
shall not preclude the Company from thereafter terminating said payments based
upon the same violation.

     15.  Arbitration.  Any dispute, claim or controversy relating to or arising
          -----------                                                           
out of this Agreement (or the breach thereof) shall be settled by final, binding
and non-appealable arbitration before the American Arbitration Association (the
"Association"), with the hearing to be held in Santa Clara or San Mateo County,
California, under the California Employment Dispute Resolution Rules then in
effect for that organization.  This Section 15 shall not be construed to limit
the Company's right to obtain relief under Section 8 with respect to any matter
or controversy subject to Section 8, and, pending a final determination by the
arbitrator with respect to any such matter or controversy, the Company shall be
entitled to obtain any such relief by direct application to a court of law,
without being required to first arbitrate such matter or controversy.
Arbitration shall be conducted before a single arbitrator selected by the
Company and the Executive.  In the event the parties cannot agree on an
arbitrator, then the Association will supply both parties with a list of seven
names from which the parties will alternately strike one name until only one
remains, first choice is determined by a coin toss.  The party winning the coin
toss has the option of striking first.  Judgment may be entered on the
arbitrator's award in any court of competent jurisdiction to prevent any
continuation of any violation of the provisions of this Agreement.  The cost of
the arbitrator, any record or transcript of the arbitration, and administrative
fees, shall be borne by the Company.  Each party shall bear the fees of their
respective attorneys, the expenses of their witnesses and any other expenses
connected with presenting their cases.

     16.  Severability.  It is mutually agreed and understood by the parties
          ------------                                                      
that should any of the agreements and covenants contained herein be determined
by any court of competent jurisdiction to be invalid by virtue of being vague or
unreasonable, including but not limited to the provisions of Sections 6 or 7,
then the parties hereto consent that this Agreement shall be amended retroactive
to the date of its execution to include the terms and conditions said court
deems to be reasonable and in conformity with the original intent of the parties
and the parties hereto consent that under such circumstances, said court shall
have the power and authority to determine what is reasonable and in conformity
with the original intent of the parties to the extent that said covenants and/or
agreements are enforceable.

     17.  Applicable Law.  This Agreement shall be construed in accordance with
          --------------                                                       
the laws of the State of California.

     18.  Amendment.  This Agreement may be amended or canceled by mutual
          ---------                                                      
Agreement of the parties in writing without the consent of any other person.

     19.  Counterparts.  This Agreement may be executed in any number of
          ------------                                                  
counterparts, each of which when so executed and delivered shall be an original,
but all such counterparts shall together constitute one and the same instrument.
Each counterpart may consist of a copy hereof 

                                      -8-
<PAGE>
 
containing multiple signature pages, each signed by one party hereto, but
together signed by both of the parties hereto.

     20.  Other Agreements.  This Agreement constitutes the sole and complete
          ----------------                                                   
Agreement between the Company and the Executive and supersedes all other
agreements, both oral and written, between the Company and the Executive with
respect to the matters contained herein including, without limitation any prior
employment agreements between the Company and the Executive.  No verbal or other
statements, inducements, or representations have been made to or relied upon by
the Executive.  The parties have read and understand this Agreement.

  Dated as of the date set forth above.


                               PACIFIC GATEWAY EXCHANGE


                               By:  /s/ Howard A. Neckowitz
                                  Its: President and Chief Executive Officer


                                  /s/ Robert F. Craver
                                      EXECUTIVE

                                      -9-
<PAGE>
 
                                   Exhibit A
                        Definition of Change in Control

     For purposes of the Agreement, a "Change in Control" shall mean the
earliest to occur of any one of the following events:

     (1)   any "Person", as such term is used in Section 13(d) and 14(d) of the
           Securities Exchange Act of 1934, as amended (the "Exchange Act")
           (other than the Company, the Executive, any corporation owned,
           directly or indirectly, by the stockholders of the Company in
           substantially the same proportions as their ownership of stock of the
           Company, and any trustee or other fiduciary holding securities under
           an employee benefit plan of the Company), becomes the "beneficial
           owner" (as defined in Rule 13d-3 promulgated under the Exchange Act),
           of 25% or more of the combined voting power of the Company's then
           outstanding securities having the right to vote for the election of
           directors ("Voting Stock");

     (2)   the majority of the Board of Directors of the Company (the "Board")
           does not consist of individuals who are Incumbent Directors, which
           term means the members of the Board on the date of this Agreement;
           provided that any person becoming a director subsequent to such date
           whose election or nomination for election was supported by three-
           quarters of the directors who then comprised the Incumbent Directors
           shall be considered to be an Incumbent Director;

     (3)   the Company adopts any plan of liquidation for the distribution of
           all or substantially all of its assets;

     (4)   the company merges with or into another company, or all or
           substantially all of the assets or business of the Company is
           disposed of pursuant to a merger, consolidation or other transaction
           (unless the shareholders of the Company immediately prior to such
           merger, consolidation or other transaction beneficially own, directly
           or indirectly, in substantially the same proportion as they owned the
           Voting Stock of the Company, all of the Voting Stock or other
           ownership interest of the entity or entities, if any, that succeed to
           the business of the Company); or

     (5)   the Company combines with any other company and is the surviving
           corporation but, immediately after the combination, the shareholders
           of the Company immediately prior to the combination hold, directly or
           indirectly, 50% or less of the Voting Stock of 

<PAGE>
 
           the combined company (there being excluded from the number of shares
           held by such shareholders, but not from the Voting Stock of the
           combined company, any shares received by affiliates of such other
           company in exchange for stock of such other company).

Once a Change in Control has occurred, no subsequent event shall be considered a
Change in Control for purposes of this Agreement.